Xây dựng danh bạ
Tichpx muốn xây dựng danh bạ liên lạc để lưu vào trong máy tính. Trong quá trình xây dựng danh bạ Tichpx để ý và thấy rằng rất nhiều từ nọ là tiền tố của từ kia. Nếu từ x được ghép bởi hai từ y và z tức là x=yz thì y được gọi là tiền tố và z gọi là hậu tố của x (Ví dụ từ tichpx có các tiền tố t, ti, tic, tich, tichp, tichpx). Trong khi cập nhật danh bạ với mỗi từ Tichpx có 1 trong hai thao tác
- add là bổ sung một liên lạc vào danh bạ
- find là tìm xem một từ là tiền tố của bao nhiêu liên lạc đã có
Bạn hãy lập trình để xác định giúp Tichpx nhé
Input
Dòng đầu chứa số nguyên dương n là số thao tác \((1<= n <= 10^5)\)
n dòng tiếp theo mỗi dòng thuộc một trong hai thao tác hoặc là add hoặc là find một liên lạc là một xâu gồm toàn chữ thường tiếng anh có độ dài không quá 30 ký tự
Output
Với mỗi thao tác find xuất ra màn hình số liên lạc đã có trong danh bạ có tiền tố muốn tìm
Ví dụ
Input
6
add daihocgiaothongvantai
add daihocthuyloi
find daihoc
add daihocxaydung
find hocvien
find daiOutput
2
0
3
Comments
dùng trick lỏ thì từ tle thành ac :))
Chắc phải nâng cấp lên bài lại là để dùng Cây tiền tố chứ anh em dùng map thế này thì ...