BGSTRING - GHÉP XÂU

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua Codeforces (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên Codeforces. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên Codeforces

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274766/problem/U

Ai bảo chăn trâu là khổ ? Thật ra hoàn toàn không phải vậy, Đại Ca Đi Học có một dàn đệ tử “sửu nhi”, sẵn sàng code bất kỳ bài toán nào mà sư phụ giao phó. Chuẩn bị cho kỳ thi PreDuyenHai, Đại Ca Đi Học bắt đầu luyện tuyệt chiêu sinh chuỗi thần thánh: Đầu tiên  có một chuỗi P, tạo ra chuỗi S như sau:

  • Bước 1 : S ban đầu là chuỗi rỗng,
  • Bước 2 : Chèn P vào S.
  • Bước i: Chọn một vị trí nào đó trong chuỗi S (có thể ở ngay đầu hoặc ở cuối xâu S), chèn P vào đó.

Ví dụ, nếu ban đầu P là hello, chuỗi S có thể sẽ như sau (chỗ chèn P được in đậm):

1)

2) hello

3)    h hello ello

4)    h hello elhellolo

5)    hhe hello lloelhellolo

Sau 5 bước, chuỗi S có thể là hhehellolloelhellolo.

Sau khi có chuỗi S, một “sửu nhi” hỏi sư phụ Đại Ca Đi Học, chuỗi P nào có thể sinh ra S?

Yêu Cầu : Cho chuỗi S, tìm chuỗi P ngắn nhất mà từ P có thể tạo thành S theo cách trên. Nếu có nhiều P, in ra chuỗi có thứ tự từ điển bé nhất.

Input

Dòng 1 chứa một xâu ký tự S, gồm các ký tự thường trong bảng chữ cái tiếng Anh. Độ dài xâu ký tự từ 1 đến 200.

Output

Xâu P ngắn nhất và có thứ tự từ điển bé nhất mà có thể tạo ra xâu S theo cách trên.

Example

Input:
hhehellolloelhellolo

Output:
hello

Xâu P ngắn nhất và có thứ tự từ điển bé nhất mà có thể tạo ra xâu S theo cách trên.


  • Người up: voj
  • Nguồn bài: Bắc Giang PreVOI 2015