KPARCH - Archiver
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.
|
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 |