## DMOPC '17 Contest 2 P4 - Mimi and Dictionary

View as PDF

Points: 12 (partial)
Time limit: 1.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 as a proper prefix of which is also a palindrome. Given a string , find the length of the longest proper prefix palindrome which appears at least twice.

#### Constraints

Let denote the length of string .

#### Input Specification

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

#### Output Specification

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

aaaa

3

#### Explanation for Sample Output 1

The longest proper prefix palindrome is aaa.

abab

1

#### Explanation for Sample Output 2

The longest proper prefix palindrome is a.

• commented on Nov. 24, 2020, 10:40 p.m. edited

Wouldnt the output for case 2 be 3?

Isnt aba a proper prefix palindrome of abab

Edit: nvm it's two occurrences

• commented on Nov. 24, 2020, 10:53 p.m.

aba is indeed a proper prefix palindrome, but it does not appear twice.

• commented on Nov. 23, 2017, 7:30 p.m.

is "proper prefix" any substring from S?

• commented on Nov. 23, 2017, 9: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.