Subtask 1:

Với mỗi mật khẩu \(X[i]\) của người dùng thứ \(i\), cần trả lời truy vấn có bao nhiêu mật khẩu khác chứa \(X[i]\) dưới dạng chuỗi con?
Đối với mỗi mật khẩu, chúng ta giải quyết các truy vấn bằng cách lặp lại tất cả các mật khẩu và kiểm tra mỗi chuỗi con có thể.

Độ phức tạp tính toán là \(O(N^2 \times L^2)\), trong đó \(N\) là số lượng người dùng và \(L\) là độ dài mật khẩu.
Như vậy với cách này chỉ có thể giải quyết được sub1 ứng 40% test của bài có \(N ≤ 2000\).

Subtask 2:

Có thể tăng tốc bằng cách tính toán trước, với mỗi mật khẩu có các chuỗi con khác nhau là gì. Để trả lời các truy vấn có bao nhiêu mật khẩu khác chứa mật khẩu người dùng thứ \(i\) làm xâu con thì ta cần đếm số lần một chuỗi con xuất hiện. Việc đếm có thể được giải quyết bằng bảng băm.

Độ phức tạp là \(O (N\times L^2)\).

tknhannguyenphu editorial:

https://hackmd.io/UruN8k1iQoq5vMUtj_Nrzg?view