Danh bạ tiền tố trực tuyến

Bối cảnh và bài toán

Một dịch vụ định danh nhận các tên tài khoản theo thời gian. Hệ thống phải thêm tên mới, kiểm tra một tên đã được đăng ký bao nhiêu lần và đếm bao nhiêu tên hiện có bắt đầu bằng một tiền tố cho trước.

Yêu cầu

Xử lý q thao tác: ADD s, COUNT s, PREFIX p. COUNT in số lần chuỗi chính xác đã được thêm; PREFIX in số chuỗi đã thêm có tiền tố p.

Input

• Dòng 1 chứa q.
• q dòng tiếp theo, mỗi dòng là một thao tác ADD s, COUNT s hoặc PREFIX p.

Output

Với mỗi thao tác COUNT hoặc PREFIX, in một số nguyên trên một dòng.

Ràng buộc

• 1 <= q <= 2 * 10^5
• Tổng độ dài các chuỗi trong input không vượt 5 * 10^5.
• Chuỗi chỉ gồm chữ cái thường a..z.

Chấm điểm

Ví dụ 1

Input

8
ADD apple
ADD app
ADD apple
PREFIX app
COUNT apple
COUNT appl
PREFIX apple
PREFIX z

Output

3
2
0
2
0

Giải thích. Có ba chuỗi đã thêm bắt đầu bằng app; apple được thêm hai lần.

Ví dụ 2

Input

5
ADD a
ADD ab
PREFIX a
COUNT a
PREFIX ab

Output

2
1
1

Giải thích. a là prefix của cả a và ab, nhưng chính xác chuỗi a chỉ xuất hiện một lần.

Gợi ý

Hãy xác định thông tin nào có thể được duy trì khi quét từng ký tự hoặc khi đi qua từng node prefix, thay vì xử lý lại toàn bộ chuỗi/tập từ sau mỗi thao tác.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.