/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 500 点
問題文
英小文字からなる文字列 A = A_1 A_2 ... A_n があります。
あなたは 1 \leq i \leq j \leq n であるような任意の二つの添字 i, j を選び、A のうち部分文字列 A_i A_{i+1} ... A_j を反転することができます。
この操作は一回まで行うことができます。
これによって得られる文字列は何通りあるでしょうか？
制約
- 1 \leq |A| \leq 200,000
- A は英小文字からなる。
入力
入力は以下の形式で標準入力から与えられる。
A
出力
A のうち任意の部分文字列を一回まで反転することによって、何通りの文字列が得られるか出力せよ。
入力例 1
aatt
出力例 1
5
得られる文字列は aatt（何もしない）、atat（A[2..3] を反転）、atta（A[2..4] を反転）、ttaa（A[1..4] を反転）、taat（A[1..3] を反転）です。
入力例 2
xxxxxxxxxx
出力例 2
1
どの部分文字列を反転しても、結果は xxxxxxxxxx です。
入力例 3
abracadabra
出力例 3
44
Score : 500 points
Problem Statement
You have a string A = A_1 A_2 ... A_n consisting of lowercase English letters.
You can choose any two indices i and j such that 1 \leq i \leq j \leq n and reverse substring A_i A_{i+1} ... A_j.
You can perform this operation at most once.
How many different strings can you obtain?
Constraints
- 1 \leq |A| \leq 200,000
- A consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
A
Output
Print the number of different strings you can obtain by reversing any substring in A at most once.
Sample Input 1
aatt
Sample Output 1
5
You can obtain aatt (don't do anything), atat (reverse A[2..3]), atta (reverse A[2..4]), ttaa (reverse A[1..4]) and taat (reverse A[1..3]).
Sample Input 2
xxxxxxxxxx
Sample Output 2
1
Whatever substring you reverse, you'll always get xxxxxxxxxx.
Sample Input 3
abracadabra
Sample Output 3
44