牛客多校 2018 第三场 E Sort String（KMP求循环节）

题目描述

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 Si 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 Si. Si and Sj will be the same group if and only if Si=Sj.
3. For each group, let Lj be the list of index i in non-decreasing order of Si in this group.
4. Sort all the Lj 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|≤ 106
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.

输入

abab

输出

2
2 0 2
2 1 3

输入

deadbeef

输出

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

链接

https://www.nowcoder.com/acm/contest/141/E

题意

给定一个长度为n的字符串s，每次通过截取第i位到第n-1位并加上前i位得到一个新的字符串p（0<=i<len）。问产生的p可能有多少种。输出每一种的数量及字符串编号（第几次产生的）。

题解

如果给定的字符串是周期串，那么组数为周期的长度，每组的数量为总长度/周期长度；如果不是，那么一定有n组。周期可以同kmp求得，最小循环节问题。好像还可以用hash做，不会。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e6 + 10;
int Next[maxn];
char P[maxn];

void getNext(int len) // 求解next数组
{
    memset(Next, 0, sizeof(Next));
    Next[0] = -1, Next[1] = 0;
    for (int i = 1; i < len; ++i)
    {
        int j = Next[i];
        while (j != -1 && P[i] != P[j])
            j = Next[j];
        Next[i+1] = j + 1; // 关键是得到next[len]
    }
}

int main()
{
    scanf("%s", P);
    int len = strlen(P);
    getNext(len);
    int k = len - Next[len]; // 最小循环节
    if (len % k == 0)
    {
        printf("%d\n", k);
        for (int i = 0; i < k; ++i)
        {
            int lenk = len / k; // 总长度/周期=每组数量
            printf("%d", lenk);
            for (int j = i; j < len; j +=k)
                printf(" %d", j);
            printf("\n");
        }
    }
    else
    {
        printf("%d\n", len);
        for (int i = 0; i < len; ++i)
            printf("1 %d\n", i);
    }
    return 0;
}

网上题解有部分代码过不了一些简单的数据，因为求得的next数组有问题，我们要得到第n位的next值而不是第n-1位的。

The end.
2018-08-05 星期日