Đếm chuỗi con

View as PDF

Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C++, Pascal, pypy3, Python

Cho một chuỗi ký tự S và một danh sách các mẫu (pattern) P₁, P₂, ..., Pₘ. Với mỗi mẫu Pᵢ, hãy đếm số lần nó xuất hiện trong chuỗi S dưới dạng chuỗi con liên tiếp (substring).

Input:

  • Dòng đầu tiên chứa một chuỗi có độ dài n
  • Dòng thứ hai chứa một số nguyên k số lượng mẫu cần kiểm tra.
  • Sau đó là k dòng, mỗi dòng chứa một mẫu (pattern) gồm các ký tự từ 'a' đến 'z'.

Output:
Với mỗi mẫu, in ra số vị trí mà mẫu đó xuất hiện trong chuỗi ban đầu.

Constraints:

  • 1 \le n \le 10^5
  • 1 \le k \le 5 \cdot 10^5
  • Tổng độ dài của tất cả các mẫu không vượt quá 5 \cdot 10^5

Example
Sample Input:

aybabtu
3
bab
abc
a

Sample Output:

1
0
2

Comments

There are no comments at the moment.