APIO '14 P1 - Palindromes

View as PDF

Submit solution

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

Problem types

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

|s| is length of string s.
A substring of string s_1s_2 \ldots s_{|s|} is any non-empty string s_is_{i+1} \ldots s_j, where 1 \le i \le j \le |s|. 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 4 \times 1 = 4
  • b has 2 occurrences in the given string, its occurrence value is 2 \times 1 = 2
  • c has 1 occurrence in the given string, its occurrence value is 1 \times 1 = 1
  • aba has 2 occurrences in the given string, its occurrence value is 2 \times 3 = 6
  • aca has 1 occurrence in the given string, its occurrence value is 1 \times 3 = 3
  • bacab has 1 occurrence in the given string, its occurrence value is 1 \times 5 = 5
  • abacaba has 1 occurrence in the given string, its occurrence value is 1 \times 7 = 7

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

Sample Input 2

www

Sample Output 2

4

Scoring

Subtask 1 (8 points)

1 \le |s| \le 100

Subtask 2 (15 points)

1 \le |s| \le 1\,000

Subtask 3 (24 points)

1 \le |s| \le 10\,000

Subtask 4 (26 points)

1 \le |s| \le 100\,000

Subtask 5 (27 points)

1 \le |s| \le 300\,000


Comments

There are no comments at the moment.