POJ 2406 KMP_综合

题意

传送门 POJ 2406

题解

$KMP$ 算法中 $b[i]$ 代表字符串区间 $[0,i-1]$ 的最长且相等的前缀与后缀长度。设字符串长度为 $len$ ，那么循环节的长度为 $len-b[len]$ ；若不满足 $len\%(len-b[len])==0$ 则 $n=1$ 。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 1000005
char s[maxn];
int b[maxn];void kmp(char *s)
{int i = 0, j = -1, len = strlen(s);b[i] = j;while (i < len){while (j >= 0 && s[i] != s[j]) j = b[j];++i, ++j;b[i] = j;}
}int main()
{while (~scanf(" %s", s) && s[0] != '.'){kmp(s);//字符串长度, 循环节长度int len = strlen(s), len2 = len - b[len];printf("%d\n", len % len2 == 0 ? len / len2 : 1);}
}