本文主要是介绍牛客网暑期多校训练赛第三场 E题 Sort String，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
题意：
给了一个字符串，Si是由下标i到字符串末尾加上0到i-1组成的字符串，只有当字符串Si和Sj是相同的才算是在一组，问字符串可以分成多少组并按字典序最小的输出每组中的i下标。
思路：
看到这题想到了哈希，然后哈希改来改去改到95%死活不过。还有9分钟的时候队友想出来了正解，可惜来不及敲了QAQ||
这题最后是如果字符串是有循环节，并且完全由循环节构成的才能进行分组。
如果没有完全由循环节构成的话，就像这样的图，将字符串复制一份到后面，会发现中间是断开的连不上。
所以知道了这点就好做了。用KMP来算循环节的大小就好了。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1e6+5;
char t[maxn];
int ne[maxn];
void makenext(const char p[],int ne[],int len)
{ne[0]=0;for(int i=1,k=0;i<len;i++){while(k>0&&p[i]!=p[k]) k=ne[k-1];if(p[i]==p[k]) k++;ne[i]=k;}
}
int main()
{int len;scanf("%s",t);len=strlen(t);makenext(t,ne,len);int c=len-ne[len-1];//循环节if(len%c==0&&ne[len-1]!=0){printf("%d\n",c);int r=len/c;//每组的个数for(int i=0;i<c;i++){int pos=i;printf("%d ",r);for(int j=1;j<=r;j++){if(j==r)printf("%d\n",pos);elseprintf("%d ",pos);pos+=c;}}}else{printf("%d\n",len);for(int i=1;i<=len;i++){printf("1 ");printf("%d\n",i-1);}}return 0;
}
这篇关于牛客网暑期多校训练赛第三场 E题 Sort String的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
