DMOPC '17 Contest 2 P4 - Mimi and Dictionary

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Mimi is playing with a dictionary when she gets a great idea! Throw random words together, give them a definition, and then make a problem about it!

For this problem, Mimi has decided to define a proper prefix palindrome of string S as a proper prefix of S which is also a palindrome. Given a string S, find the length of the longest proper prefix palindrome which appears at least twice.

Constraints

Let |S| denote the length of string S.

Subtask 1 [10%]

1 \le |S| \le 100

Subtask 2 [20%]

1 \le |S| \le 1\,000

Subtask 3 [70%]

1 \le |S| \le 10^5

Input Specification

The first and only line of input will contain of a single string S, consists of only lowercase letters.

Output Specification

The length of the longest proper prefix palindrome which appears at least twice.

Sample Input 1

aaaa

Sample Output 1

3

Explanation for Sample Output 1

The longest proper prefix palindrome is aaa.

Sample Input 2

abab

Sample Output 2

1

Explanation for Sample Output 2

The longest proper prefix palindrome is a.


Comments


  • 0
    Jerry_Gu  commented on Nov. 23, 2017, 2:30 p.m.

    is "proper prefix" any substring from S?


    • 2
      aeternalis1  commented on Nov. 23, 2017, 4:05 p.m. edited

      Any substring that is a prefix of S is a "proper prefix".

      For example abcd is a proper prefix of abcdefg, but defg is not.

      Furthermore, a proper prefix cannot be equal to the entire string nor can it be empty.