題目鏈接：http://poj.org/problem?id=1961

題目大意：給出一個長為n的字符串，求到每個字符之前有多少個字串循環(huán)次數(shù)大于1

方法： kmp ，求出這個字符串的next數(shù)組。在字符串位數(shù)是i-next[i]的整數(shù)倍是。輸出字串循環(huán)次數(shù)。

#include <iostream> #include <cstdio> #include <algorithm> #include <string>using namespace std; int next[1000010]; char str[1000010];void getnext(char *s, int len) {int i = 0;int j = -1;next[0] = -1;while(i < len){if(j == -1 || str[i] == str[j])next[++i] = ++j;elsej = next[j];} } int main() {int n;int cas = 0;while(~scanf("%d",&n) && n){scanf("%s",str);getnext(str,n);printf("Test case #%d\n",++cas);for(int i=1;i<=n;i++){int d = i - next[i];if(next[i] && i % (i-next[i])== 0)printf("%d %d\n",i, i/(i-next[i]));} printf("\n");}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/llguanli/p/8399174.html

總結(jié)

以上是生活随笔為你收集整理的poj 1961 Period（KMP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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