Xâu Con Xuất Hiện Duy Nhất Ngắn Nhất

Buổi 56 — Suffix Array & LCP Strings
Points
50
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
string
Submissions
Đề bài

Một phòng thí nghiệm sinh học lưu trữ trình tự mã di truyền dưới dạng một xâu $S$ gồm $N$ chữ cái tiếng Anh in thường. Để phân biệt mẫu vật này với phần còn lại của chính nó, các nhà nghiên cứu cần tìm một dấu ấn phân tử — tức là một xâu con liên tiếp khác rỗng của $S$ chỉ xuất hiện đúng 1 lần trong $S$. Hãy tìm dấu ấn phân tử có độ dài ngắn nhất; nếu có nhiều xâu con cùng đạt độ dài nhỏ nhất, hãy in ra xâu có thứ tự từ điển nhỏ nhất.

Dữ liệu vào

Một dòng duy nhất chứa xâu $S$ ($1 \le |S| \le 10^5$) chỉ gồm các chữ cái in thường từ 'a' đến 'z'.

Dữ liệu ra

In ra xâu con xuất hiện đúng 1 lần có độ dài ngắn nhất (và nhỏ nhất theo thứ tự từ điển nếu có nhiều đáp án cùng độ dài).

Ví dụ
Input Output
abacaba c
Giới hạn

Thời gian: 1.0s, Bộ nhớ: 256MB.

Draft saved