Cho một xâu ký tự chính có độ dài và một tập hợp gồm xâu truy vấn . Tất cả các ký tự trong các xâu này đều thuộc tập hợp ký tự .
Nhiệm vụ của bạn là với mỗi xâu truy vấn , hãy tìm độ dài lớn nhất sao cho tiền tố độ dài của xuất hiện như một chuỗi con liên tiếp (substring) bên trong xâu chính .
Nói cách khác, với mỗi , hãy tìm sao cho là một chuỗi con của .
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên dương và , lần lượt là độ dài của xâu chính và số lượng xâu truy vấn.
Dòng thứ hai chứa xâu chính có độ dài . Các ký tự thuộc tập .
dòng tiếp theo, mỗi dòng chứa một xâu truy vấn . Các ký tự thuộc tập .
Kết quả:
Gồm dòng tương ứng với xâu truy vấn.
Mỗi dòng in ra một số nguyên duy nhất là độ dài của tiền tố dài nhất tìm được cho xâu truy vấn đó.
Ví dụ:
Dữ liệu:
7 3
SNNSSNS
NNSS
NNN
WSEE
Kết quả:
4
2
0
Giới hạn: , đảm bảo độ dài mỗi đoạn văn bản mật mã nhỏ hơn hoặc bằng .
