KMP，在有循环节的前提下： 循环节 t = len-next[len]， 个数num = len/(len-next[len]);

个人理解，如果有循环节，循环节长度必定小于等于len/2, 换句话说next[len]>=len/2;

对于len%(len-next)!=0的这种情况不讨论，循环节不存在。

下面是假设循环节存在的情况

当次数等于2， 对于abcabc这种情况就不用说了，len = 6, next[len] = 3;

当次数大于2，

对于串a1 a2 a3 a4 a5 a6 a7 a8 a9

如果有

a1 a2 a3 a4 a5 a6 

         a4 a5 a6 a7 a8 a9

next[len] = 6, len = 9;

说明a7 a8 a9 = a4 a5 a6;

   a1 a2 a3 = a4 a5 a6;

循环节就很明显了，其它情况也是类似与这样讨论。

所以。。。。。

view code#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;const int N = 1e6+10;char s[N];int next[N];void getnext(char *s, int *next, int len){    int j=0, i=1;    next[1] = 0;    while(i<len)    {        if(j==0 || s[i]==s[j]) next[++i] = ++j;        else j = next[j];    }}int getsub(char *s, bool flag, int len){    int i = 0, j = 1, k = 0;    while(i<len && j<len && k<len)    {        if(i==j) j++;        int ni = i+k, nj = j+k;        if(ni>=len) ni -= len;        if(nj>=len) nj -= len;        if(s[ni]>s[nj])        {            if(flag) i += k+1;            else j += k+1;            k = 0;        }        else if(s[ni]<s[nj])        {            if(flag) j+= k+1;            else i+= k+1;            k = 0;        }        else k++;    }    return i;}int main(){    while(scanf("%s", s)>0)    {        int len = strlen(s);        getnext(s, next, len);        int t = len-next[len];        t = (len%t?1:len/t);        int minsub = getsub(s, true, len)+1;        int maxsub = getsub(s, false, len)+1;        printf("%d %d %d %d\n",minsub, t, maxsub, t);    }}