## APIO '14 P1 - Palindromes

View as PDF

Points: 25 (partial)
Time limit: 0.6s
Memory limit: 128M

Problem types
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

You are given a string of lower-case Latin letters. Let us define a substring's "occurrence value" as the number of the substring occurrences in the string multiplied by the length of the substring. For a given string find the largest occurrence value of palindromic substrings.

#### Notes

is length of string .
A substring of string is any non-empty string , where . Any string is also its own substring.
A string is called palindromic, if it reads the same in either direction: from left to right and from right to left.

#### Input Specification

The only line of input contains a non-empty string of lower-case Latin letters (a-z).

#### Output Specification

Output one integer – the largest occurrence value of palindromic substrings.

#### Sample Input 1

abacaba

#### Sample Output 1

7

#### Explanation for Sample Output 1

There are seven palindromic substrings a, b, c, aba, aca, bacab, abacaba.

• a has 4 occurrences in the given string, its occurrence value is
• b has 2 occurrences in the given string, its occurrence value is
• c has 1 occurrence in the given string, its occurrence value is
• aba has 2 occurrences in the given string, its occurrence value is
• aca has 1 occurrence in the given string, its occurrence value is
• bacab has 1 occurrence in the given string, its occurrence value is
• abacaba has 1 occurrence in the given string, its occurrence value is

So, the largest occurrence value of palindromic substrings is 7.

#### Sample Input 2

www

#### Sample Output 2

4