/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
以下の条件を満たす英小文字からなる文字列を良い文字列とします。
- 1 文字以下を書き換えることで回文にすることができる。
例えば a、iwai、abcdcza などは良い文字列ですが、abcd、atcoder などは良い文字列ではありません。特に、回文も良い文字列であることに注意してください。
英小文字からなる文字列 S が与えられます。
S の空でない部分文字列（連続な部分列）であって良い文字列であるものの個数を求めてください。
2 つの部分文字列は、S から取り出す場所が異なれば文字列として等しくても区別して数えることに注意してください。
部分文字列とは
S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。
例えば、ab は abc の部分文字列ですが、ac は abc の部分文字列ではありません。
制約
- S は英小文字からなる長さ 1 以上 10^4 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
ababa
出力例 1
13
S の 2 文字目から 3 文字目までの ba や 1 文字目から 5 文字目までの ababa などが良い文字列です。
良い文字列は部分文字列 15 通りのうち 1 文字目から 4 文字目までの abab、2 文字目から 5 文字目までの baba を除く 13 通りです。
入力例 2
atcoder
出力例 2
18
入力例 3
abccbacbacb
出力例 3
40
Score : 400 points
Problem Statement
A string consisting of lowercase English letters is called a good string if it satisfies the following condition.
- It can be turned into a palindrome by rewriting at most one character.
For example, a, iwai, and abcdcza are good strings, but abcd and atcoder are not good strings. Note that, in particular, a palindrome is also a good string.
You are given a string S consisting of lowercase English letters.
Find the number of non-empty substrings (contiguous subsequences) of S that are good strings.
Two substrings taken from different positions of S are counted separately even if they are equal as strings.
What is a substring?
A substring of S is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S.
For example, ab is a substring of abc, but ac is not a substring of abc.
Constraints
- S is a string of length between 1 and 10^4, inclusive, consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
S
Output
Output the answer.
Sample Input 1
ababa
Sample Output 1
13
The substring ba from the 2nd through 3rd characters of S and the substring ababa from the 1st through 5th characters are some good strings.
Among the 15 substrings, the good strings are the 13 substrings other than abab from the 1st through 4th characters and baba from the 2nd through 5th characters.
Sample Input 2
atcoder
Sample Output 2
18
Sample Input 3
abccbacbacb
Sample Output 3
40