題目鏈接：點擊查看

題目大意：現(xiàn)在規(guī)定想要制作一串珍珠手鏈，需要用到兩段一模一樣的字符串首位相接而成，現(xiàn)在給定一個字符串，問最少需要添加幾個珍珠才能滿足條件

題目分析：一開始以為是個簡單的模擬題，但后來想到了很多特殊的樣例讓自己無從下手，后來知道了原來是要用kmp的next數(shù)組的一個小性質(zhì)：

設(shè)len=n-next[n]，則len就是當(dāng)前字符串的循環(huán)節(jié)，若n%len==0，則說明該字符串是周期性字符串

有了這個性質(zhì)，我們就可以直接先求出next數(shù)組，然后來判斷缺少多少個珠子了

注意一下這個題目的數(shù)據(jù)量很大，所以要用char字符串，用string類的話會超時，但不知道為什么用了cin加速外掛會WA掉。。所以還是老老實實用scanf和char字符串吧

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;char s[N];int nx[N];void getnext(char s[]) {int len=strlen(s);nx[0]=-1;int i=0,j=-1;while(i<len){if(j==-1||s[i]==s[j])nx[++i]=++j;elsej=nx[j];} }int main() { // freopen("input.txt","r",stdin);int w;cin>>w;while(w--){scanf("%s",s);int n=strlen(s);getnext(s); // for(int i=0;i<n;i++) // cout<<nx[i]<<' '; // cout<<endl;int len=n-nx[n];if(len!=0&&n%len==0&&n/len>1)//若當(dāng)前字符串已經(jīng)滿足條件，則無需添加珠子 printf("0\n");else//否則輸出還差幾個珠子 printf("%d\n",len-n%len);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 3746 Cyclic Nacklace(KMP的next数组判循环节)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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