Contest Edu #1 - Baby String

View as PDF

Submit solution

Points: 0.50
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Một chuỗi t được gọi là Chuỗi Em bé của chuỗi s khi thỏa mãn cả 3 điều kiện sau:

  • ~t~ là tiền tố của ~s~;
  • ~t~ là hậu tố của ~s~;
  • ~t~ xuất hiện trong ~s~ nhiều hơn ~3~ lần.
  1. Tiền tố của chuỗi s có độ dài ~l~ ~(1 \leq l \leq |s|)~ là chuỗi con bắt đầu tại vị trí ~0~ và kết thúc tại vị trí ~l - 1~.
  2. Hậu tố của chuỗi s có độ dài ~l~ ~(1 \leq l \leq |s|)~ là chuỗi con bắt đầu tại vị trí ~|s| - l~ và kết thúc tại ~|s| - 1~.

Yêu cầu

  • Cho một chuỗi ~s~, độ dài ~|s|~, và ~q~ truy vấn ~l_1,l_2,...,l_q~.
  • Đối với mỗi truy vấn ~l_i~, bạn phải kiểm tra xem tiền tố của ~s~ có độ dài ~l_i~ có phải là Chuỗi Em bé của ~s~ không và đếm số lần xuất hiện của tiền tố này trong ~s~.

Dữ liệu

  • Dòng đầu tiên chứa chuỗi ~s~ ~(1 \leq |s| \leq 10^5)~. Chuỗi chỉ bao gồm các chữ cái tiếng Anh in hoa.
  • Dòng thứ hai của đầu vào chứa số nguyên dương ~q~, ~(1 \leq q \leq 10^5)~ là số lượng truy vấn.
  • ~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~l_i~, ~(1 \leq l_i \leq |s|)~.

Kết quả

In ra ~q~ dòng, dòng thứ ~i~ là câu trả lời cho truy vấn thứ ~i~. Với truy vấn thứ ~i~, nếu tiền tố độ dài ~l_i~ của ~s~ là Chuỗi Em bé của ~s~ thì in YES và in số lần xâu con đó xuất hiện trong chuỗi ~s~; ngược lại, in NO.

Ví dụ

Sample Input
AAACMMTACMAA
4
1
2
3
4
Sample Output
YES 6
YES 3
NO
NO
Giải thích
  • Xâu con A là Chuỗi Em bé và xuất hiện 6 lần.
  • Xâu con AAA không là Chuỗi Em bé vì AAA không phải hậu tố của ~s~.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.