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 underlined characters indicate the ones that match when shift = 3.


hide comments
anish1712: 2020-07-04 22:18:57

Why does same solution gives segmentation error in C++14 and passes in C++?

hemant1612: 2019-12-17 21:24:05

Passed in 2.06 s without fast I/O.

Last edit: 2019-12-18 13:19:03
tarun2619: 2018-06-23 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: 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