Problem D
Double String
SoCCat has a string $S$ consisting of lowercase English letters a to z. For their Final Year Project, SoCCat is interested in the so-called double string.
Formally, a string $T$ is a double string if and only if:
-
$T$ has even length.
-
The first half of $T$ is equal to the second half of $T$. In other words, $T_i = T_{i + \frac{|T|}{2}}$ for all $1 \leq i \leq \frac{|T|}{2}$.
Help SoCCat count the number of pairs of indices $(i, j)$ such that $1 \leq i < j \leq |S|$ and the substring $S[i, j] = S_i S_{i+1} \dots S_{j}$ is a double string!
Input
The input contains a string $S$ ($1 \leq |S| \leq 200\, 000$) consisting of lowercase English letters a to z.
Output
Output a single integer denoting the number of pairs of indices $(i, j)$ such that $1 \leq i < j \leq |S|$ and the substring $S[i, j]$ is a double string.
Explanation of Sample Inputs
In the first sample, $S = \texttt{mississippi}$. All the substrings that are double strings are:
-
$\texttt{ississ}$, with $i = 2$ and $j = 7$.
-
$\texttt{ssissi}$, with $i = 3$ and $j = 8$.
-
$\texttt{ss}$, with $i = 3$ and $j = 4$.
-
$\texttt{ss}$, with $i = 6$ and $j = 7$.
-
$\texttt{pp}$, with $i = 9$ and $j = 10$.
Thus, the answer is $5$.
In the second sample, $S = \texttt{aaaaa}$. All pairs of indices $(i, j)$ such that $j-i+1$ is even are double strings. Thus, the answer is $6$.
In the third sample, $S = \texttt{soc}$. There are no double strings in this case, so the answer is $0$.
| Sample Input 1 | Sample Output 1 |
|---|---|
mississippi |
5 |
| Sample Input 2 | Sample Output 2 |
|---|---|
aaaaa |
6 |
| Sample Input 3 | Sample Output 3 |
|---|---|
soc |
0 |
