e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Ukrainian Selection Camp to the European Girls' Olympiad in Informatics 2021

Містер А та паліндроми

Містер Б подарував Містеру А рядок $s$, що складається з маленьких літер латинського алфавіту. Друзі визначили цікавість непорожньої стрічки $t$, як кількість входжень цієї стрічки $t$ в стрічку $s$ помножена на довжину стрічки $t$. Ваше завдання~--- знайти максимальну цікавість серед всіх непорожніх стрічок які є паліндромами. Паліндромом вважається стрічка що читається однаково з обох сторін. \InputFile Перший рядок містить один рядок $s$ $(1\le |s|\le 3\cdot 10^5)$. \OutputFile Виведіть одне ціле число~--- максимальну цікавість серед всіх непорожніх стрічок які є паліндромами. \Note У першому прикладі паліндром, що складається з однієї літери <<\t{a}>> має чотири входження у рядок $s$, однак найбільшу цікавість має паліндром <<\t{abacaba}>>. \Scoring \begin{enumerate} \item ($8$ балів): $1\le |s|\le 100$; \item ($15$ балів): $1\le |s|\le 1\,000$; \item ($24$ бали): $1\le |s|\le 10\,000$; \item ($26$ балів): $1\le |s|\le 100\,000$; \item ($27$ балів): без додаткових обмежень. \end{enumerate}
Time limit 1 second
Memory limit 256 MiB
Input example #1
abacaba
Output example #1
7
Input example #2
www
Output example #2
4
Author Ihor Barenblat