MAXMATCH - Maximum Self-Matching

no tags 

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.

Input

The first and only line of input contains the string s. 2 <= |s| <= 105.

Output

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.

Example

Input:
caccacaa

Output:
4
3

Explanation:

caccacaa
caccacaa


The bold characters indicate the ones that match when shift = 3.


hide comments
Noureldin Yosri: 2015-01-20 15:25:53

I don't believe it, writing my own complex struct improved the performance by ~40%

TL is very strict

Shaka Shadows: 2011-08-22 15:30:59

Time limit too strict. I get TLE/WA with the same code :(.

[Rampage] Blue.Mary: 2011-08-22 15:30:59

Time limit is somewhat strict, some constant optimization is needed.

re: I think it's fine even if you're looking at characters one by one. Bin Jin however found a way to solve all three at once! :)

Last edit: 2011-06-12 10:41:55
Bin Jin: 2011-08-22 15:30:59

the testcases are weak, my submission which failed on "aab" got accepted.

re: I'll add some more. That code of yours passes the cases in which the solution has a big shift, and fails the random ones :O

Last edit: 2011-06-11 08:56:40

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