#1934 · Chuỗi trong chuỗi

Cho một chuỗi ký tự S và Q truy vấn. Mỗi truy vấn yêu cầu xác định số lần một chuỗi ký tự M_i xuất hiện trong một đoạn con xác định của chuỗi S.

Cụ thể: Với mỗi truy vấn i: Xác định số lần chuỗi M_i xuất hiện trong đoạn [l_i, r_i] (tính từ ký tự l_i đến ký tự r_i trong chuỗi S).

• Dòng đầu tiên chứa chuỗi S và số lượng truy vấn Q (cách nhau bởi khoảng trắng).
• Tiếp theo là Q dòng, mỗi dòng chứa:
  • Hai số nguyên l_i, r_i (đoạn cần xét trong chuỗi S).
  • Một chuỗi M_i (chuỗi cần đếm số lần xuất hiện).

Gồm Q dòng, mỗi dòng là số lần chuỗi M_i xuất hiện trong đoạn [l_i, r_i] của chuỗi S.