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

View as PDF

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

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 of a single string , 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.

• commented on Nov. 24, 2020, 5: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, 5:53 p.m.

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

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

is "proper prefix" any substring from S?

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