Задача №113597. Тяжелые палиндромы
Палиндром - это слово, которое читается справа налево также, как слева направо. Например, "a", "abba", "anavolimilovana" - палиндромы.
Весом строки, состоящей из строчных латинских символов будем называть количество ее подстрок (слов), являющихся палиндромами (при этом каждое вхождение подстроки считается отдельно). Формально, пусть W - строка длины N . Слово w a , b - подстрока W , состоящая из символов на позициях с индексами с a по b включительно. Вес строки W - это количество пар целых чисел a , b ( 1 ≤ a , b ≤ N ) таких, что w a , b является палиндромом.
Вам дана строка, состоящая из строчных латинских символов. Вы можете либо оставить ее неизменной, либо поменять любой из ее символов на любой другой символ. Найдите максимально возможный вес строки, которую вы можете получить.
Первая строка содержит одну строку W ( 1 ≤ | W | ≤ 100000 ), состоящую из строчных латинских символов.
Выведите одно целое число - максимально возможный вес.
Решения, работающие при
|
W
| ≤ 100
, будут оцениваться в 17 баллов.
Решения, работающие при
|
W
| ≤ 5000
, будут оцениваться еще в 37 баллов.
aaaa
10
baccb
9
slavko
7