KPARCH - Archiver

no tags 

One of your friends wants to write his own archiver. He is going to replace neighboring equal substrings with only one copy. For example, he is going to change substring "AA" with something like "2(A)" and if "A" is long enough it will reduce the file size.

But, before performing any coding stuff he wants to know how many such double substrings are there in the input file.

He asks you to help him, because this task is very difficult for him.

Input

Input file contains the text to be archived. It will only contain Latin letters (big and small). Its size will not exceed 200000 symbols. Letters are case sensitive, i.e. "X" is not equal to "x".

Output

Write a number of substrings of input text which can be written as "AA", i.e. consist of two equal concatenated parts.

Example

Input:
abcdefg

Output:
0
Input:
blabla

Output:
1
Input:
aCacaacaa

Output:
4

hide comments
[Trichromatic] XilinX: 2009-11-22 12:29:59

Mmm... Using suffix array, the total time complexity O(nlogn) leads to TLE. Maybe only an algorithm with time complexity O(n) can pass.

Edit: Finally I find that this problem requires O(nlogn) algorithm, only extended KMP algorithm can pass.

Last edit: 2009-12-07 04:55:25

Added by:Pavel Kuznetsov
Date:2008-04-11
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:IT Festival Arkhangelsk 2007