題面:http://poj.org/problem?id=1961

本題的重點在于如果一個串是周期串的話,那么每次錯位的位置應該是一個循環節。所以當i-next[i]=x*i時,此時next[i]就是一個循環節。Code: #include <iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<stdlib.h> #include<vector> #include<queue> #include<vector> using namespace std; #define INF 0xfffffff #define N 1000010 char s[N]; int next[N]; void kmp(int k) {int i,j=-1;next[0] = -1;for(i = 1 ; i < k ; i++){while(j>-1&&s[i]!=s[j+1])j = next[j];if(s[i]==s[j+1])j++;next[i] = j;} } int main() {int n,i;int kk=1;while(scanf("%d",&n)!=EOF){if(!n) break;memset(next,0,sizeof(next));for(i = 0 ; i < n ; i++)scanf("%c",&s[i]);kmp(n);printf("Test case #%d\n",kk++);for(i = 0 ;i < n ; i++)if(next[i]!=-1&&(i+1)%(i-next[i])==0){printf("%d %d\n",i+1,(i+1)/(i-next[i]));}puts("");}return 0; }

轉載于:https://www.cnblogs.com/ukcxrtjr/p/11195033.html

總結

以上是生活随笔為你收集整理的POJ 1961的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。