poj1961 kmp

题目大意，求这个字符串到i为止有多少个循环串；

int k = i-next[i];
if((i+1)%k == 0 && (i+1)!= k)
printf("%d %d\n", i+1, (i+1)/k);

这是代码的主要部分，求next数组的部分大家都知道，我来说说这部分的正确性；

例如一个字符串的第99为指向第96位，也就是说后4-99位和前1-96位是匹配的，就是说94到96与97到99是是匹配的；

而且91-94与94-96是匹配的。。。。。。。。。。。

一直可以推到最前面，以上就是正确性啦~

上代码

#include <iostream>
#include <string.h>
#include <map>
#include <stdio.h>
using namespace std;
const int maxa =1000005;
int next[maxa];
int vis[maxa];
int n;
void init_kmp(char str[])
{
memset(vis, 0, sizeof(vis));
next[0]=-1;
for(int i=1;str[i]!=0;i++)
{
int j= next[i-1];
while(str[j+1]!=str[i]&&j>=0)
j= next[j];
if(str[j+1] == str[i])
next[i] = j + 1;
else
next[i] = -1;
}
}
int main(){
char str[maxa];
int d =1;
while(scanf("%d", &n), n){
scanf("%s", str);
printf("Test case #%d\n", d++);
init_kmp(str);
for(int i = 0; i < n; i++){
int k = i-next[i];
if((i+1)%k == 0 && (i+1)!= k)
printf("%d %d\n", i+1, (i+1)/k);
}
printf("\n");
}
}

poj1961 kmp,布布扣,bubuko.com

poj1961 kmp

原文：http://www.cnblogs.com/icodefive/p/3856183.html