DMOPC '17 Contest 2 P4 - Mimi and Dictionary

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 $S$ ~S~ as a proper prefix of $S$ ~S~ which is also a palindrome. Given a string $S$ ~S~, find the length of the longest proper prefix palindrome which appears at least twice.

Constraints

Let $|S|$ ~|S|~ denote the length of string $S$ ~S~.

Subtask 1 [10%]

$1 \le |S| \le 100$ ~1 \le |S| \le 100~

Subtask 2 [20%]

$1 \le |S| \le 1\,000$ ~1 \le |S| \le 1\,000~

Subtask 3 [70%]

$1 \le |S| \le 10^5$ ~1 \le |S| \le 10^5~

Input Specification

The first and only line of input will contain a single string $S$ ~S~, consisting 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

Explanation for Sample Output 1

The longest proper prefix palindrome is aaa.

Sample Input 2

abab

Sample Output 2

Explanation for Sample Output 2

The longest proper prefix palindrome is a.

Comments

0

krish338 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

1

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

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

0

Jerry_Gu commented on Nov. 23, 2017, 7:30 p.m. ← edited →

is "proper prefix" any substring from $S$ ~S~?

2

aeternalis1 commented on Nov. 23, 2017, 9:05 p.m. ← edit 2 →

Any substring that is a prefix of $S$ ~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.