本文主要是介绍@牛客网暑期ACM多校训练营（第三场） E: Sort String (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 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
输出
复制
8 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7
[题意]
串 S , 构造Si, 然后 将Si 相同的放在一起, 然后 分成 k 组, 每组 输出 组内 数目 以及 每个Si 的下标
Si 由 i 开始 到结尾 + 0-i 组成
例如 abab
a:"abab" + "",
b: "bab"+"a"
a: "ab" + "ab"
b: "b" + "aba"
[思路]
利用KMP 计算 串S 的循环节, 然后, 输出循环节的个数 就是 k ,从 0 开始 每次加 循环节
[代码]
#include <bits/stdc++.h>
#include <stdlib.h>
#include <utility>
#define findx(x,b,n) lower_bound(b+1,b+1+n,x)-b
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w",stdout)
#define SHUT ios_base::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(20); cout.tie(nullptr); cin.tie(nullptr);
#define lson rt << 1, l, mid
#define rson rt << 1|1, mid + 1, r#pragma comment(linker, "/STACK:1024000000,1024000000") // 扩栈
//next_permutation(a+1,a+x) 全排列
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())using namespace std;typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;const double PI=acos(-1.0);
const int INF=0x3f3f3f3f;
const double esp=1e-6;
const int maxn=1e6+155;
const int MOD=1e9+7;
const int mod=1e9+7;
int dir[5][2]={0,1,0,-1,1,0,-1,0};/*********************************head************************/char str[maxn];
int net[maxn];
void getfail(char p[]) //字符串p自我匹配
{int len=strlen(p);net[0]=net[1]=0;for(int i=1;i<len;i++){int j=net[i];while(j&&p[i]!=p[j])j=net[j];if(p[i]==p[j])net[i+1]=j+1;//多匹配到了一个字符elsenet[i+1]=0;//该字符配不上}
}int main()
{scanf("%s",str);getfail(str);int len = strlen(str);int d;if( len % (len - net[len]) ==0){d = len/(len-net[len]);//cout<<"d is "<<d<<endl;}elsed = 1;printf("%d\n",len/d);rep(i,0,len/d){printf("%d ",d);rep(j,0,d){printf("%d%c",i+j*(len/d),j==(d-1)?'\n':' ');}}//如果len% (len - next[len]) == 0，那么循环节的循环次数为len / (len -next[len])，否则为1return 0;
}
这篇关于@牛客网暑期ACM多校训练营（第三场） E: Sort String (KMP 循环节)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
