牛客网 牛客网暑期ACM多校训练营（第三场）E KMP

链接：https://www.nowcoder.com/acm/contest/141/E

题目描述

Eddy likes to play with string which is a sequence of characters. One day, Eddy has played with a string S for a long time and wonders how could make it more enjoyable. Eddy comes up with following procedure:

1. For each i in [0,|S|-1], let S_i be the substring of S starting from i-th character to the end followed by the substring of first i characters of S. Index of string starts from 0.
2. Group up all the S_i. S_i and S_j will be the same group if and only if S_i=S_j.
3. For each group, let L_j be the list of index i in non-decreasing order of S_i in this group.
4. Sort all the L_j by lexicographical order.

Eddy can't find any efficient way to compute the final result. As one of his best friend, you come to help him compute the answer!

输入描述:

Input contains only one line consisting of a string S.

1≤ |S|≤ 10

⁶

S only contains lowercase English letters(i.e. 

).

输出描述:

First, output one line containing an integer K indicating the number of lists.
For each following K lines, output each list in lexicographical order.
For each list, output its length followed by the indexes in it separated by a single space.

示例1

输入

abab

输出

2
2 0 2
2 1 3

示例2

输入

deadbeef

输出

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

题意   给定一个字符串T 设长度为n   然由这个字符串产生出n个字符串s0...sn-1  si=Ti-Tn-1+T0-Ti-1 将si相同的分到一组   i 按照从小到大排序 输出分组后的 i 序列

解析   我们可以推导一下 若T是不循环的 那么没有相同的  若是循环的 最小循环节为len 那么共有len 组   i 就属于 i%len这一组

　　　KMP判断是否循环 且找出最小循环节长度  随便 保存一下 也可以哈希。。。

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define fillchar(a, x) memset(a, x, sizeof(a))
#define huan printf("
");
#define debug(a,b) cout<<a<<" "<<b<<" ";
using namespace std;
typedef long long ll;
const int maxn=1e6+10,inf=0x3f3f3f3f;
const ll mod=1e9+7;
char t[maxn];
int _next[maxn];
int tlen,slen;
void getnext()
{
    int j,k;
    j=0,k=-1,_next[0]=-1;
    while(j<=tlen)
        if(k==-1||t[j]==t[k])
            _next[++j]=++k;
        else
            k=_next[k];
}
int main()
{
    while(scanf("%s",t)!=EOF)
    {
        tlen=strlen(t);
        set<int> s[tlen+10];
        getnext();
        if(tlen%(tlen-_next[tlen])==0)
        {
            int len=tlen-_next[tlen];
            for(int i=0;i<tlen;i++)
                s[i%len].insert(i);
            printf("%d
",len);
            for(int i=0;i<len;i++)
            {
                printf("%d",s[i].size());
                for(auto it=s[i].begin();it!=s[i].end();it++)
                {
                    printf(" %d",*it);
                }
                huan;
             }
        }
        else
        {
            printf("%d
",tlen);
            for(int i=0;i<tlen;i++)
                printf("%d %d
",1,i);
        }
    }
}