Subtask 1:

• Với mỗi truy vấn ta duyệt lại ~26~ kí tự từ ‘a’ đến ‘z’, với mỗi kí tự ta lại duyệt lại xâu để lấy ra vị trí đầu và cuối của chúng rồi cộng hiệu vị trí cuối và đầu vào kết quả. (Độ phức tạp: ~O(N * Q * 26)~)

Subtask 2:

• Với mỗi kí tự, ta lưu 1 vector chứa các vị trí xuất hiện của chúng. Mỗi truy vấn ta sẽ duyệt lại ~26~ kí tự và dùng tìm kiếm nhị phân để lấy được vị trí đầu và cuối của chúng. (Độ phức tạp: ~O(N * 26 * log_2(N))~)

Subtask 3:

• Nhận thấy với mỗi truy vấn, ta có thể thực hiện bước cộng tất cả vị trí kết thúc trước và trừ đi tất cả vị trí bắt đầu sau. Vì vậy ta sẽ xử lí truy vấn offline.
• Ta sẽ lưu lại ~N~ vector, vector thứ ~i~ chứa những truy vấn kết thúc tại ~i~.
• Duyệt xâu ~S~ từ ~1~ đến ~N~, với mỗi kí tự, sẽ lưu lại vị trí gần nhất mà nó xuất hiện. Sau khi duyệt đến vị trí thứ ~i~, với mỗi truy vấn trong vector thứ ~i~, ta sẽ duyệt ~26~ kí tự, xem vị trí cuối cùng của nó có nằm trong đoạn truy vấn không, nếu có ta sẽ cộng vào kết quả của truy vấn đó.
• Tương tự với phần trừ, chỉ khác là ta sẽ xây vector thứ ~i~ là các truy vấn bắt đầu ở ~i~, duyệt xâu ~S~ từ ~N~ về ~1~, và thay vì cộng vào kết quả thì chúng ta sẽ trừ đi. (Độ phức tạp: ~O((N + Q) * 26)~)