/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
英小文字からなる文字列 S が与えられます．S のすべての連続する部分文字列 |S|(|S|+1)/2 個に対して以下の問題を解き，解の値の総和を求めてください．
問題：英小文字からなる文字列 T が与えられます．T に以下の操作を好きなだけ繰返すことで作ることのできる文字列の長さの最小値を求めてください．
- T の接頭辞であって奇数長（2k+1 文字とする）の回文になっているものを任意に取る．T の先頭 k 文字を削除する．
制約
- 1\leq |S|\leq 10^6
- S は英小文字からなる
入力
入力は以下の形式で標準入力から与えられる．
S
出力
答えを出力せよ．
入力例 1
abab
出力例 1
16
T が a または b のとき，答えは 1 です．
T が ab または ba のとき，答えは 2 です．
T が aba または bab のとき，k=1 として操作を一度行うのが最適であり，答えは 2 です．
T が abab のとき，k=1 として操作を行ったあと，もう一度 k=1 として操作を行うのが最適であり，答えは 2 です．
よって全体の答えは 1\times 4 + 2\times 3 + 2\times 2 + 2\times 1 = 16 です．
入力例 2
abacaba
出力例 2
67
入力例 3
tabatadebatabata
出力例 3
739
Score : 100 points
Problem Statement
You are given a string S consisting of lowercase letters. For each contiguous substring of S (there are |S|(|S|+1)/2 such substrings), solve the following problem, and compute the sum of the answers.
Problem: You are given a string T consisting of lowercase letters. Compute the minimum possible length of a string that can be obtained from T by repeatedly applying the following operation an arbitrary number of times.
- Take a prefix of T that is a palindrome of odd length. Let the length be 2k+1. Remove the first k letters of T.
Constraints
- 1\leq |S|\leq 10^6
- S consists of lowercase letters.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
abab
Sample Output 1
16
If T is a or b, the answer is 1.
If T is ab or ba, the answer is 2.
If T is aba or bab, applying the operation with k=1 once is optimal, and the answer is 2.
If T is abab, applying the operation with k=1 twice is optimal, and the answer is 2.
Therefore, the whole answer is 1\times 4 + 2\times 3 + 2\times 2 + 2\times 1 = 16.
Sample Input 2
abacaba
Sample Output 2
67
Sample Input 3
tabatadebatabata
Sample Output 3
739