## APIO '14 P1 - Palindromes

View as PDF

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

Problem types

You are given a string of lowercase 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 the 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 lowercase 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