7
POJ1961 Period（KMP next）
source link: https://arminli.com/poj1961/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Armin's Blog
POJ1961 Period（KMP next）
March 13, 2016
POJ2406的加强版，2406 是求一个字符串中循环节次数，而这道题是输出所有前 i 个字符构成的字符串的循环节次数，所以在求 next 数组中，每求出一次就判断一次是否有循环节，如果有就输出。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
using namespace std;
char a[1000005];
int nextt[1000005], l;
void kmp_pre(char x[],int m,int nextt[]){
int i, j;
j = nextt[0] = -1;
i = 0;
while(i < m){
while(-1!=j && x[i]!=x[j])
j = nextt[j];
nextt[++i] = ++j;
if(nextt[i]!=0 && i%(i-nextt[i]) == 0){
int ans = i/(i-nextt[i]);
cout << i << " " << ans << endl;
}
}
}
int main(){
//freopen("a.txt", "r", stdin);
int n, cas = 1;
while(~scanf("%d", &n) && n){
scanf("%s", a);
printf("Test case #%d\n", cas++);
kmp_pre(a, n, nextt);
cout << endl;
}
return 0;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK