시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 6 | 2 | 2 | 33.333% |
A string t is called a smooth transformation of a string w if there exist an integer m ≥ 1 and strings w0, w1, . . . , wm such that:
You are given a string s = s1s2 . . . s|s|. Find the number of triplets of indices (i, j, k) such that 1 ≤ i < j < k ≤ |s| and si..k = sisi+1 . . . sk is a smooth transformation of si..j = sisi+1 . . . sj.
The only line of the input contains the string s (4 ≤ |s| ≤ 105) consisting of lowercase English letters.
Display the sought number of triplets.
abcababc
5
In the example test case, the triplets are (1, 3, 6), (3, 4, 6), (3, 4, 8), (4, 5, 7), and (5, 6, 8).