소문자 알파벳으로 이루어진 문자열 \(S\)가 주어진다.

어떤 (비어 있지 않은) 문자열 \(w\)에 대해, \(w\)를 두 번 이어 붙인 문자열 \(ww\)를 쌍둥이라고 부른다. 예를 들어 \(w=\texttt{ab}\)이면 \(ww=\texttt{abab}\)이 쌍둥이이다.

\(S\)의 연속한 부분문자열 중 쌍둥이인 것이 몇 가지나 되는지 구하여라. 단, 문자열로서 서로 다른 것만 세며, \(S\) 안에서 여러 번 등장하더라도 같은 문자열이면 한 번만 센다.

예를 들어 \(S = \texttt{aabaab}\)이면 쌍둥이인 부분문자열은 \(\texttt{aa}\), \(\texttt{aabaab}\) 두 가지이다.

\(1 \le |S| \le 100{,}000\)

\(S\)는 소문자 알파벳('a'~'z')으로만 이루어진다.

한 줄에 문자열 \(S\)가 주어진다. \(S\)는 비어 있지 않으며 소문자 알파벳으로만 이루어진다.

\(S\)의 서로 다른 쌍둥이 부분문자열의 개수를 한 줄에 출력한다.

riseoj 작성

출처 Original