Số xâu con tốt

Điểm: 5,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$ và $n$ luật. Mỗi luật là một bộ ba $(p, l, r)$ , trong đó $p$ là một xâu và $l, r$ là hai số nguyên không âm $(l \leq r)$ .

Ta nói xâu $t$ thoả mãn luật $(p, l, r)$ nếu số lần xuất hiện của $t$ trong $p$ nằm trong đoạn $[l, r]$ (tính cả hai đầu). Số lần xuất hiện của xâu $t$ trong xâu $p$ là số cặp chỉ số $(i, j)$ với $1 \leq i \leq j \leq | p |$ sao cho $p [i . . j] = t$ (cho phép các lần xuất hiện chồng lên nhau).

Một xâu $t$ được gọi là tốt nếu nó thoả mãn tất cả $n$ luật đã cho.

Hãy đếm số xâu con khác nhau của $s$ là xâu tốt. Hai xâu con $s [x . . y]$ và $s [z . . w]$ được coi là khác nhau khi và chỉ khi $s [x . . y] \neq s [z . . w]$ (so sánh nội dung xâu, không so sánh vị trí).

Dữ liệu vào

Dòng đầu chứa xâu $s$ .
Dòng thứ hai chứa số nguyên $n$ .
$n$ dòng tiếp theo, mỗi dòng chứa một xâu $p_{i}$ và hai số nguyên $l_{i}, r_{i}$ cách nhau bởi dấu cách $(0 \leq l_{i} \leq r_{i} \leq | p_{i} |)$ .

Tất cả các xâu cho trước đều khác rỗng và chỉ gồm các chữ cái Latinh thường.

Dữ liệu ra

Một số nguyên — số xâu con khác nhau của $s$ là xâu tốt.

Ràng buộc

$0 \leq n \leq 10$ .
$| s |, | p_{i} | \leq 200$ .

Ví dụ

Input	Output	Giải thích
aaab 2 aa 0 0 aab 1 1	3	Ba xâu tốt là «aab», «ab» và «b». Các xâu con khác hoặc chứa «aa» (vi phạm luật 1) hoặc không xuất hiện trong «aab» (vi phạm luật 2).
ltntlnen 3 n 0 0 ttlneenl 1 4 lelllt 1 1	2	Chỉ hai xâu «e» và «t» thoả mãn cả ba luật.
a 0	1	Khi không có luật nào, mọi xâu con đều tốt — $s$ chỉ có một xâu con duy nhất là «a».

Bình luận

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