本文主要是介绍KMP——Period，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Period
Time Limit: 1000MS Memory limit: 65536K
题目描述
For each prefix of a given string S with N characters (each character has an
ASCII code between 97 and 126, inclusive), we want to know whether the prefix
is a periodic string. That is, for each i (2 ≤ i ≤ N) we want to know the largest K
> 1 (if there is one) such that the prefix of S with length i can be written as AK ,
that is A concatenated K times, for some string A. Of course, we also want to
know the period K.
输入
The input file consists of several test cases. Each test case consists of two
lines. The first one contains N (2 <= N <= 1 000 000) – the size of the string S.
The second line contains the string S. The input file ends with a line, having the
number zero on it.
输出
For each test case, output “Test case #” and the consecutive test case
number on a single line; then, for each prefix with length i that has a period K >
1, output the prefix size i and the period K separated by a single space; the
prefix sizes must be in increasing order. Print a blank line after each test case.
示例输入
3 aaa 12 aabaabaabaab 0
示例输出
Test case #1 2 2 3 3 Test case #2 2 2 6 2 9 3 12 4
提示
这道题目是KMP问题，求得是字串的个数和位置， 可以利用求next值来计算，如图所示，而i - j就是最小字串的长度，i指示当前母串的长度，只要i能对j整除，则除数就是字串的相同个数。
求自身的next值，当i与j匹配的时候，i和j前移，移动之后的i所对应的next值是j，代表了在该元素前面前缀等于后缀的最大长度为j，而j又是从0开始增长的，也就是从第一个元素算起，要计算循环的字符串，用i-j代表了j所代表的字符串的第一个字符对应的i所代表的字符串的前边的字符数目，也就是一个循环节的长度，在用i总长度去除单位长度，就会得到循环的次数。而确定一段字符串是循环节的条件就是i的长度是循环节的整倍数，并且不是本身自己（即i/(i-j) > 1）。
![]()
![]()
#include <stdio.h>
#include <string.h>
#include <stdlib.h>char st[1000009];
char st1[1000009];
int next[1000009];
int main()
{int i,j,l,n,x,y,m,a,b;l = 0;while(scanf("%d",&n)&&n){l++;scanf("%s",st);printf("Test case #%d\n",l);i = 0;j = -1;next[0] = -1;while(i<n){if(j == -1 || st[i] == st[j]){i++;j++;if(i%(i-j) == 0 && i/(i-j) >1)printf("%d %d\n",i,i/(i-j));next[i] = j;}elsej = next[j];}printf("\n");}return 0;
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>char st[1000009];
char st1[1000009];
int next[1000009];
int main()
{int i,j,l,n,x,y,m,a,b;l = 0;while(scanf("%d",&n)&&n){l++;scanf("%s",st);printf("Test case #%d\n",l);i = 0;j = -1;next[0] = -1;while(i<n){if(j == -1 || st[i] == st[j]){i++;j++;if(i%(i-j) == 0 && i/(i-j) >1)printf("%d %d\n",i,i/(i-j));next[i] = j;}elsej = next[j];}printf("\n");}return 0;
}
这篇关于KMP——Period的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
