牛客网暑期ACM多校训练营(第三场): E. Sort String（KMP ）next数组的应用

101 阅读 0 评论 67 点赞

我是靠谱客的博主可靠咖啡，这篇文章主要介绍牛客网暑期ACM多校训练营(第三场): E. Sort String（KMP ）next数组的应用，现在分享给大家，希望可以做个参考。

链接：https://www.nowcoder.com/acm/contest/141/E
来源：牛客网

Sort String

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

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.

示例1

输入

复制

abab

输出

复制

2
2 0 2
2 1 3

示例2

输入

复制

deadbeef

输出

复制

题意：给出一行字符串找到最小循环部分

输出：一共有多少个循环节并输出每一字符循环个数每一个循环位置；

例如；abababab（最小循环部分为 ab）

输出：
2 （有两个最大循环节：abab abab）
4 0 2 4 6 （a字符循环的个数位置）
4 1 3 5 7

思路：通过next数组找到最小循环节如果 k% (k - next[k]) == 0 则说明是由最小循环节构成的。

代码：

#include <bits/stdc++.h>
using namespace std;
 
const int M = 1e6+10;
char str[M];
int nex[M];
 
void getNext(int tlen) {//获取next数组
    int j = 0, k = -1;
    nex[0] = -1;
    while (j < tlen) {
        if (k == -1 || str[j] == str[k]) 
            nex[++j] = ++k;
        else 
            k = nex[k];
    }
}
 
int main() {
   ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> str;
    int len = strlen(str);
    getNext(len);//获取next数组
    int x = len - nex[len];
    if (len % x != 0) {
        cout << len << 'n';
        for(int i = 0; i < len; i++) 
            cout << 1 << ' ' << i << 'n';
    }
    else {
        cout << x << 'n';
        for(int i = 0; i < x; i++) {
            cout << len / x;
            for(int j = i; j < len; j += x)
                cout << ' ' << j;
            puts("");
        }
    }
    return 0;
}