Xâu Con Xuất Hiện Duy Nhất Ngắn Nhất
Points
50
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
string
Đề 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.
Community Discussion