MAXMATCH  Maximum SelfMatching
You're given a string s consisting of letters 'a', 'b' and 'c'.
The matching function m_{s}( i ) is defined as the number of matching characters of s and its ishift. In other words, m_{s}( i ) is the number of characters that are matched when you align the 0th character of s with the ith character of its copy.
You are asked to compute the maximum of m_{s}( 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.
Input
The first and only line of input contains the string s. 2 <= s <= 10^{5}.
Output
The first line of output contains the maximal m_{s}( i ) over all i.
The second line of output contains all the i's for which m_{s}( i ) reaches maximum.
Example
Input: caccacaa Output: 4
3
Explanation:caccacaa
caccacaa
The bold characters indicate the ones that match when shift = 3.
hide comments
tarun2619:
20180623 13:39:04
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. 

Noureldin Yosri:
20150120 15:25:53
I don't believe it, writing my own complex struct improved the performance by ~40%


Shaka Shadows:
20110822 15:30:59
Time limit too strict. I get TLE/WA with the same code :(. 

[Rampage] Blue.Mary:
20110822 15:30:59
Time limit is somewhat strict, some constant optimization is needed.


Bin Jin:
20110822 15:30:59
the testcases are weak, my submission which failed on "aab" got accepted.

Added by:  gustav 
Date:  20110610 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own problem 