trang chủ / đề bài / icpc22_mt_b

Xâu Baby

Đề bài

Mô tả

Xâu t được gọi là xâu Baby của xâu s nếu:

  • t là tiền tố của s;
  • t là hậu tố của s;
  • t xuất hiện trong s (dưới dạng xâu con liên tiếp) ít nhất 3 lần. Các lần xuất hiện được phép chồng lên nhau.

Tiền tố độ dài l (1≤l≤|s|) của s là xâu s[0…l−1], hậu tố độ dài l là xâu s[|s|−l…|s|−1].

Cho xâu s và q truy vấn l1,…,lq. Với mỗi truy vấn li, hãy kiểm tra tiền tố độ dài li của s có phải là xâu Baby của s hay không, và nếu có thì đếm số lần nó xuất hiện trong s.

Dữ liệu vào

Dòng đầu tiên chứa xâu s (1≤|s|≤105) chỉ gồm các chữ cái tiếng Anh in hoa.

Dòng thứ hai chứa số nguyên q (1≤q≤105) là số truy vấn. Mỗi dòng trong q dòng tiếp theo chứa một số nguyên li (1≤li≤|s|).

Dữ liệu ra

Với mỗi truy vấn in kết quả trên một dòng: nếu tiền tố độ dài li là xâu Baby của s thì in YES, một dấu cách và số lần nó xuất hiện trong s; ngược lại in NO.

Ràng buộc

  • 1≤|s|≤105, s chỉ gồm chữ cái in hoa.
  • 1≤q≤105, 1≤li≤|s|.

Ví dụ

Input Output Giải thích
AAACMMTACMAA
4
1
2
3
4
YES 6
YES 3
NO
NO
"A" xuất hiện 6 lần, "AA" xuất hiện 3 lần (ở vị trí 0, 1 và 10); "AAA" và "AAAC" không phải hậu tố.
ABABABABAB
5
1
2
3
4
5
NO
YES 5
NO
YES 4
NO
Chỉ "AB" và "ABAB" vừa là tiền tố vừa là hậu tố; chúng xuất hiện 5 và 4 lần.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0