Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BGSTRING - GHÉP XÂ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)    hhelloello

4)    hhelloelhellolo

5)    hhehellolloelhellolo

 

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.


Được gửi lên bởi:VOJ Team
Ngày:2015-12-09
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:Bắc Giang PreVOI 2015

hide comments
2018-09-05 16:40:02
hà vũ huy phong đẹp trai nhất thế giới
2017-11-28 16:24:04
rất khắm và rất bựa
2016-06-04 15:48:52
khửa
2016-01-01 03:43:28 ChienTran


Last edit: 2016-01-01 04:28:39
2015-12-22 04:48:31
I was wondering if after all these years you'd like to meet
2015-12-16 17:10:36 shaha
it's me
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.