Chuỗi mắc xích

View as PDF

Submit solution

Points: 1.03 (partial)
Time limit: 2.47s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Sưu tầm
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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 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à ab ~a~ và ~a~ ba (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.

Sample Input

abbaabbaa

Sample Output

5

Comments

Please read the guidelines before commenting.


There are no comments at the moment.