Truy vấn xâu con có trọng số
Đề bài
Mô tả
Cho xâu đôi một khác nhau. Xâu thứ là và có trọng số . Cho thêm một xâu văn bản .
Với mỗi truy vấn (đánh số từ , tính cả hai đầu), xét xâu con
Giá trị của xâu con được định nghĩa là
trong đó là số lần (có thể chồng lên nhau) xuất hiện dưới dạng một xâu con liên tiếp của . Với mỗi truy vấn, hãy in ra .
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và ().
- dòng tiếp theo, mỗi dòng chứa một xâu và một số nguyên (). Các xâu đôi một khác nhau.
- Dòng tiếp theo chứa xâu văn bản .
- dòng cuối cùng, mỗi dòng chứa hai số nguyên và mô tả một truy vấn.
Các đảm bảo thêm:
- Tổng độ dài của tất cả các xâu trong dữ liệu vào (mọi và ) không vượt quá .
- Tổng số lần xuất hiện của tất cả các trong không vượt quá .
Dữ liệu ra
In ra dòng, dòng thứ chứa một số nguyên là đáp án của truy vấn thứ .
Ràng buộc
- , .
- .
- Các xâu và chỉ gồm chữ cái tiếng Anh in thường.
- Tổng độ dài các xâu và không vượt quá ; tổng số lần xuất hiện của các trong không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 3 she 3 he 2 her 5 sh 1 er 4 us 2 ushersheher 1 5 2 4 6 8 |
17 6 6 |
Truy vấn là xâu usher: she, he, her, sh, er, us mỗi xâu xuất hiện lần, tổng . Truy vấn là she: . Truy vấn là she: . |
| 3 4 a 1 aa 10 aaa 100 aaaa 1 4 2 3 1 1 2 4 |
234 12 1 123 |
Ví dụ bổ sung (không có trong đề gốc). Trong aaaa: a xuất hiện lần, aa lần, aaa lần (các lần xuất hiện được chồng lên nhau): . |
Bình luận