0
POJ2406 Power Strings（KMP next）
source link: https://arminli.com/poj2406/
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
POJ2406 Power Strings（KMP next）
March 13, 2016
题意：求一个字符串中长度最短的循环节的循环次数。
KMP 中的 next 数组代表前缀与后缀相等的最长长度。
例如： a b a b a b
next:-1 0 0 1 2 3 4
next[n]==4,代表着，前缀与后缀相等的最长长度是 4（abab），若 l%(l-next[l]) == 0 则证明存在循环节。
#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];
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;
}
}
int main(){
//freopen("a.txt", "r", stdin);
while(~scanf("%s", a) && a[0] != '.'){
int l = strlen(a);
kmp_pre(a, l, nextt);
if(l%(l-nextt[l]) == 0){
int ans = l/(l-nextt[l]);
cout << ans << endl;
}
else cout << "1" << endl;
}
return 0;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK