#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.

• 1≤∣S∣≤100,000: Độ dài của chuỗi S.
• 1≤Q≤100,000: Số lượng truy vấn.
• 1≤∣M_i∣≤100,000: Độ dài chuỗi M_i của từng truy vấn.
• $0≤l_i≤r_i <∣S∣$: Đoạn con nằm trong giới hạn chuỗi $S$.
• Tổng độ dài các chuỗi M_i trong tất cả các truy vấn không vượt quá 2,000,000.
• Chuỗi S và M_i chỉ chứa các ký tự viết thường từ a đến z.