嫦娥奔月（KMP循环节）

一道关于循环节的问题，牛客上的题，这里的题面变了，但确实是同一道题。
题目
《归妹》卦辞为：昔者恒我（姮娥）窃毋死之药于西王母，服之以（奔）月。将往，而枚占于有黄。有黄占之曰：“吉。翩翩归妹，独将西行。逢天晦芒，毋惊毋恐，后且大昌”。恒我遂托身于月，是为蟾蠩。
嫦娥去了广寒宫以后每天特别无聊，只有小兔子陪她玩。有一天，天蓬元帅来找她去东海玩，虽然她很想出去玩，可是她是后羿的妻子啊，心里又喜欢吴刚，更何况玉帝还在那盯着呢，怎么可以随随便便和他出去呢？于是她出了一道题给天蓬，答应只要他做出来了就随他一起去东海。
题目如下:
1.对于一个字符串S，定义以下n个字符串，S[i]表示一个这样的字符串：截取S的前i个字符，让截取部分的第一个字符接在剩下部分的最后一个字符后面。例：对于字符串S =“abcdef”，S[2]表示字符串“cdefab”。
2.将n个字符串进行分组，相同字符串为一组。
3.定义序列L，表示为每一组的字符串的编号按从小到大排列的序列。
4.按照L的字典序从小到大输出所有分组。
例：S =“abab”，S[0] =“abab”，S[1] =“baba”，S[2] =“abab”，S[3] =“baba”。分组L[]为(0, 2)，(1, 3)。对L数组排序后：L[1]=(0, 2)，L[2]=(1, 3)。因为0比1小。
这题太难了，为了成功的约到嫦娥，天蓬找到了你来帮忙，你能帮帮他吗？

输入描述
输入包含一个字符串S。
1 ≤ |S| ≤ 1000000。
S只包含小写字母。

输出描述
第一行输出一个整数K，表示分组个数。
接着K行，每行第一个整数n表示该分组有多少个字符串，后面接着n个整数，表示该分组的字符串的编号。
样例输入
abab

deadbeef
样例输出
2
2 0 2
2 1 3

8
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7

题意：
就是从第一个字母开始，把他们逐个放在字符串的末尾，看这个字符串是不是一个新的字符串，如果是，把他们整理到一组，这组每个数表示开始的字母的在字符串中的下标，每行第一个数表示一共有多少个相同的，结果要按照每一组数字的字典序排列。

这个主要是找该字符串的循环节，首先先求出该字符串的next数组，若该字符串的长度为m，则该字符串的循环节长度为l=m-next【m-1】；
找到循环节后，看他是否能被该字符串的长度整除，如果不可以，说明每组只有一共数，可以分成m组；如果可以整出，那么可以分成m/l组，每组有l个数，可以直接列出来。

代码：：

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;

char s[1000005];
int next[1000005];
int m;

void g_next(char *b,int *n)
{
    memset(n,0,sizeof(n));
    int k=0;
    n[0]=0;
    for(int q=1;q<m;q++){
        while(k > 0&&b[q] != b[k])
            k=n[k-1];
        if(b[k] == b[q])
            k+=1;
        n[q]=k;
    }

}

int main()
{
    scanf("%s",s);
    m=strlen(s);
    g_next(s,next);
    int l=m-next[m-1];
    //printf("%d\n",l);
    if(m%l != 0){
        printf("%d\n",m);
        for(int i=0;i<m;i++){
            printf("%d %d\n",1,i);
        }
    }
    else{
        printf("%d\n",l);
        for(int i=0;i<l;i++){
            printf("%d",m/l);
            for(int j=i;j<m;j+=l){
                printf(" %d",j);
            }
            printf("\n");
        }
    }
    return 0;
}

结束