MAXMATCH - Maximum Self-Matching
You're given a string s consisting of letters 'a', 'b' and 'c'.
The matching function ms( i ) is defined as the number of matching characters of s and its i-shift. In other words, ms( i ) is the number of characters that are matched when you align the 0-th character of s with the i-th character of its copy.
You are asked to compute the maximum of ms( i ) for all i ( 1 <= i <= |s| ). To make it a bit harder, you should also output all the optimal i's in increasing order.
The first and only line of input contains the string s. 2 <= |s| <= 105.
The first line of output contains the maximal ms( i ) over all i.
The second line of output contains all the i's for which ms( i ) reaches maximum.
Input: caccacaa Output: 4
The bold characters indicate the ones that match when shift = 3.
The comments below are very old, now even with a decent implementation (only the idea is needed to solve the problem), this problem can be easily solved in the given time limit.
I don't believe it, writing my own complex struct improved the performance by ~40%
Time limit too strict. I get TLE/WA with the same code :(.
Time limit is somewhat strict, some constant optimization is needed.
the testcases are weak, my submission which failed on "aab" got accepted.