Tiền Tố Định Danh Ngắn Nhất

Buổi 55 — Trie & Aho-Corasick
Points
48
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Submissions
Đề bài

Cho danh sách gồm $N$ từ $S_1, S_2, \dots, S_N$. Với mỗi từ $S_i$, hãy tìm tiền tố khác rỗng ngắn nhất của $S_i$ mà không phải là tiền tố của bất kỳ từ $S_j$ nào khác ($j \neq i$). Nếu không tồn tại tiền tố như vậy, in ra NONE.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 10^5$).
  • $N$ dòng tiếp theo, mỗi dòng chứa một từ $S_i$.
Dữ liệu ra
  • Gồm $N$ dòng, dòng thứ $i$ là tiền tố định danh ngắn nhất của $S_i$ hoặc NONE.
Ví dụ
Input Output
4
zebra
dog
duck
dove
z
dog
du
dov
Giới hạn
  • Tổng độ dài các từ không vượt quá $10^6$.
  • Các ký tự đều thuộc a–z.
Draft saved