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.|

DTCSTR - Chuỗi mắc xích

Sắp có một biểu đình đả đảo những đề bài do pirate viết ra. Lý do đơn giản là vì chúng quá dài và quá sến. pirate rất buồn khi nghe được điều đó. Nếu bắt anh ta thay đổi thì chẳng khác nào giết chết tâm hồn thi ca trong một con người. Nhưng vì tình yêu với mọi người, pirate quyết định đây là đề bài dài và sến cuối cùng mà anh sẽ viết ra.

Một ngày nọ, đang nghiên cứu môn stringology, anh chàng nổi hứng chuyển sang nghiên cứu môn philosophy (để chuẩn bị cho những năm tháng sẽ bị nó hành hạ sau này). Sau một ngày hì hục bên bên chồng sách về "Tư tưởng Hồ Chí Minh" và "Chủ nghĩa xã hội khoa học", anh ngẫm ra chân lý của cuộc sống : Mọi sự vật hiện hữu ở hiện tại đều do một sự vật hiện hữu ở quá khứ tạo thành, giống như những mắc xích của sự tiến hóa. Ngay lập tức, pirate áp dụng nó vào các chuỗi.

Vấn đề đặt ra là cho một chuỗi S, bạn hãy xác định độ dài của chuỗi A thỏa hai điều kiện sau:

  • Chuỗi S phải phân tích được ra thành nhiều mắc xích. Mỗi mắc xích do một dãy các ký tự liên tiếp của S tạo thành và là một chuỗi A. Mỗi ký tự của chuỗi S phải thuộc vào ít nhất một mắc xích. Ví dụ: S = ababa được tạo thành từ mắc xích là abaaba (khi ghép hai chuỗi này và để phần in đậm trùng lên nhau thì được chuỗi S).
  • Độ dài chuỗi A phải là nhỏ nhất.

Input

Dữ liệu vào gồm các ký tự in thường viết liên tiếp nhau tạo thành chuỗi S (độ dài không quá 500000).

Output

Dữ liệu ra gồm một dòng duy nhất là độ dài của chuỗi A cần tìm.

Example

Input:
abbaabbaa

Output:
5

Được gửi lên bởi:khanhptnk
Ngày:2009-05-16
Thời gian chạy:1.640s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PDF PERL PHP PIKE PS PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE
Nguồn bài:Sưu tầm

hide comments
2017-10-03 15:07:44
Bài này có thể dùng KMP, Suffix Array hay Hash, v.v... đều được nhé
2016-12-10 02:59:10 Lê Hoàng Vũ
Các bạn có thể tham khảo Prefix Array đối với bài này
2016-11-15 10:19:04
1 con vij

Last edit: 2016-11-22 10:01:48
2016-07-25 10:21:50


Last edit: 2016-07-25 10:21:59
2015-07-07 10:01:36 Anh Vu
livw: theo mình nghĩ là ra 2.
2014-11-27 18:48:33 livw
neu day la xxx thi key qua la bao nhieu vay?
2009-06-22 06:15:03 Huy Luu
Sến như mọi khi =))
2009-05-22 04:58:25 ~!(*(@*!@^&
aaabaaabaaa -> là ghép của aaabaaa 2 lần, đè nhau ở 3 chữ a có được ko?
2009-05-17 16:29:09 Nguyễn Xuân Khánh
Khó hiểu hay là không hiểu ?
2009-05-16 22:49:18 AnhDQ
tớ cũng thuộc trường phái hâm mộ ra đề kiểu dài dài sến sến :"> nhưng đề này thì khó hiểu quá :| :-??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.