題目描述：

? ? 給你一個字符串S，你要對字符串S的每一位i將前i位的字符串移動到尾部形成一個新的字符串，如果形成的字符串相同則歸為一類Li。現(xiàn)在讓你將Li類按照字典序排序，并讓你輸出每一類的數(shù)量和每一類中字符串對應的下標i。

題目分析：

? ? 觀察可以發(fā)現(xiàn)，將字符串移動形成新的字符串，當且僅當字符串中存在循環(huán)節(jié)時，才會出現(xiàn)新構(gòu)成的字符串相同。因此這個問題就轉(zhuǎn)化成求一個字符串的循環(huán)節(jié)的問題。

? ? 至此，這個問題就可以用kmp中的next數(shù)組進行計算。（有一個重要結(jié)論，如果對于一個長度為L的字符串，如果L%(L-next[L])==0則代表它具有循環(huán)節(jié)，且循環(huán)節(jié)的長度為L-next[L]）

代碼：

#include <bits/stdc++.h> #define maxn 1000005 using namespace std; int nex[maxn]; char str[maxn]; void get_next(char *s){//獲取next數(shù)組int i,j;j=nex[0]=-1;i=0;int len=strlen(s);while(i<len){while(j!=-1&&s[i]!=s[j]) j=nex[j];nex[++i]=++j;} } int main() {scanf("%s",str);get_next(str);int len=strlen(str);int tmp=len-nex[len];if(len%tmp!=0){//如果沒有循環(huán)節(jié)，則每個都類都為1cout<<len<<endl;for(int i=0;i<len;i++){printf("1 %d\n",i);}}else{cout<<tmp<<endl;//字符串的種類的數(shù)目為循環(huán)節(jié)的長度for(int i=0;i<tmp;i++){cout<<len/tmp;//每個字符串種類的個數(shù)for(int j=i;j<len;j+=tmp){cout<<" "<<j;}puts("");}}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Chen-Jr/p/11007256.html

總結(jié)

以上是生活随笔為你收集整理的2018牛客暑假多校三 E（KMP运用）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。