Số xâu con tốt

Điểm: 8,00 (OI)

Giới hạn thời gian: 4.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho xâu $s$ chỉ gồm các chữ cái Latinh in thường. Với một xâu $t$ khác rỗng, ta gọi tập kí tự của $t$ là tập hợp các kí tự xuất hiện trong $t$ . Ví dụ, tập kí tự của xâu aab là ${a, b}$ .

Xét xâu con $s [a, b] = s_{a} s_{a + 1} \dots s_{b}$ (với $1 \leq a \leq b \leq | s |$ ). Hai xâu con được coi là khác nhau nếu chúng nằm ở hai vị trí khác nhau, kể cả khi nội dung giống hệt.

Cho trước một tập kí tự $C$ khác rỗng. Một xâu con $s [a, b]$ có tập kí tự bằng đúng $C$ được gọi là cực đại theo bao hàm nếu không tồn tại xâu con $s [x, y]$ nào của $s$ thỏa mãn $1 \leq x \leq a$ và $b \leq y \leq | s |$ , $y - x + 1 > b - a + 1$ , và tập kí tự của $s [x, y]$ cũng bằng $C$ .

Ký hiệu $r (C, s)$ là số lượng xâu con cực đại theo bao hàm có tập kí tự đúng bằng $C$ .

Cho xâu $s$ và $m$ tập kí tự $C_{1}, C_{2}, \dots, C_{m}$ (mỗi tập được mô tả bằng một xâu không có kí tự lặp). Với mỗi $i$ , hãy tính $r (C_{i}, s)$ .

Dữ liệu vào

Dòng đầu chứa xâu $s$ khác rỗng.
Dòng thứ hai chứa số nguyên $m$ .
Tiếp theo là $m$ dòng, dòng thứ $i$ chứa một xâu $c_{i}$ gồm các kí tự khác nhau, mô tả tập $C_{i}$ .

Dữ liệu ra

In ra $m$ số nguyên, mỗi số trên một dòng — giá trị $r (C_{i}, s)$ tương ứng.

Ràng buộc

$1 \leq | s | \leq 10^{6}$
$1 \leq m \leq 10^{4}$
Mọi kí tự trong các xâu đều là chữ cái Latinh in thường.
Các kí tự trong mỗi $c_{i}$ đôi một khác nhau. Các tập $C_{i}$ không nhất thiết phân biệt.

Ví dụ

Input	Output	Giải thích
abacaba 3 ac ba a	1 2 4	Với $C = {a, c}$ : chỉ có xâu con `abaca` (vị trí 1..5) có tập kí tự ${a, b, c}$ … nhưng cực đại theo bao hàm cho tập đúng ${a, c}$ là `aca` (vị trí 3..5), trả về $1$ . Với $C = {b, a}$ : hai đoạn cực đại là `aba` (1..3) và `aba` (5..7). Với $C = {a}$ : bốn vị trí đơn lẻ `a` (1, 3, 5, 7) là cực đại.
aaaaa 2 a a	1 1	Toàn xâu `aaaaa` là xâu con cực đại duy nhất có tập kí tự ${a}$ . Hai truy vấn giống nhau đều cho kết quả $1$ .

Bình luận

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