Ghép xâu
Đề bài
Mô tả
Cho xâu có không quá ký tự. Bạn cần xử lý truy vấn, truy vấn thứ () thuộc một trong các loại sau:
1 u c: tạo xâu mới bằng cách thêm ký tự vào cuối xâu , tức là .2 u c: tạo xâu mới bằng cách thêm ký tự vào đầu xâu , tức là .3 u v: tạo xâu mới bằng cách nối hai xâu và , tức là .4 u: tạo xâu mới là xâu đảo ngược của , tức là .5 u v: đặt . Xét mọi xâu có dạng , trong đó là một tiền tố khác rỗng của và là một hậu tố khác rỗng của . Hãy đếm số xâu phân biệt trong số đó.
Lưu ý rằng ở truy vấn thứ ta luôn tạo ra một xâu mới , còn mọi xâu đã tạo trước đó vẫn giữ nguyên.
Dữ liệu vào
- Dòng đầu tiên chứa xâu khác rỗng gồm không quá chữ cái tiếng Anh in thường.
- Dòng thứ hai chứa số nguyên , số truy vấn.
- dòng tiếp theo, dòng thứ mô tả truy vấn thứ theo một trong năm loại ở trên. Mọi tham số của truy vấn thứ thỏa mãn , và là một chữ cái tiếng Anh in thường.
Dữ liệu ra
Với mỗi truy vấn loại , in ra một dòng chứa số xâu phân biệt. Vì số này có thể rất lớn, hãy in ra phần dư của nó khi chia cho .
Ràng buộc
- .
- .
- với truy vấn thứ .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| ab 5 1 0 z 2 0 y 3 1 0 4 2 5 2 4 |
7 | Các xâu được tạo: , , , , , . Ở truy vấn thứ , các tiền tố của là , , ; các hậu tố của là , , . Ghép lại được xâu: , , , , , , , , , trong đó có xâu phân biệt. |
| a 5 5 0 0 1 1 a 5 2 2 4 3 5 4 0 |
1 3 2 |
Ví dụ bổ sung (không có trong đề gốc). , , , , . Với và ta được các xâu , , . Với và ta được , . |
Bình luận