P3649 [APIO2014] Palindrome

You are given a string $s$ consisting of lowercase Latin letters. We define the existence value of a substring of $s$ as the number of occurrences of this substring in $s$ multiplied by its length. For the given string $s$, find the maximum existence value among all palindromic substrings.

One line, a non-empty string $s$ consisting of lowercase Latin letters (a~z).

Output a single integer, the maximum existence value among all palindromic substrings.

Sample Explanation 1 Use $\lvert s \rvert$ to denote the length of string $s$. A substring of a string $s_1 s_2 \dots s_{\lvert s \rvert}$ is a non-empty string $s_i s_{i+1} \dots s_j$, where $1 \leq i \leq j \leq \lvert s \rvert$. Every string is a substring of itself. A string is called a palindrome if and only if it reads the same from left to right and from right to left. In this sample, there are $7$ palindromic substrings a, b, c, aba, aca, bacab, abacaba. Their existence values are $4, 2, 1, 6, 3, 5, 7$, respectively. Therefore, the maximum existence value among palindromic substrings is $7$. Subtasks - Subtask 1 (8 points): $1 \leq \lvert s \rvert \leq 100$. - Subtask 2 (15 points): $1 \leq \lvert s \rvert \leq 1000$. - Subtask 3 (24 points): $1 \leq \lvert s \rvert \leq 10000$. - Subtask 4 (26 points): $1 \leq \lvert s \rvert \leq 100000$. - Subtask 5 (27 points): $1 \leq \lvert s \rvert \leq 300000$. Translated by ChatGPT 5