PKU 1961(KMP判断循环段位置)

偏执的太偏执、 2022-10-02 08:58 4阅读 0赞

/\*

基本题意：给一个字符串，如果在前 i 位置处满足连续循环A^K（A：单位循环段，

K：循环个数），则输出i和K

这题跟pku 2406差不多

YY : kmp 保存 next\[i\]，如果满足 i能被单位长度（i - next\[i\]）整除，说明

（i - next\[i\]）是单位循环段A，i /(i - next\[i\])也就是K。

举两个例子应该就能理解

**　　　　例一：**

**　　　　　　i : 　　 12345678**

**　　　　　　字符串 : abababab**

**　　　　　　next\[i\]: 00123456**

这个例子假如当i等于8时，next\[i\] = 6; K也就是4，如果你有“ 你只是看

了后面\[next\[i\]+1,i \] 这一段，不能代表全部是循环，可能中间有的地方跟

你说的循环点不一样？”这种问题的话，看下面个例子

**　　　　例二：**

**　　　　　　i : 1234567**

**　　　　　　字符串 : abcabab**

**　　　　　　next\[i\]: 0001200**

这个例子中位置6.7就是你想的情况,但next\[i\] = 0;所以是不可能出现循环点的，

而位置4.5即便next\[i\] != 0,但i不能整除（i - next\[i\]),所以也不会是循环段。

\*/

代码如下

#include <stdio.h>
    #include <string.h>
    char s[1000003];
    int next[1000003];
    int len;
    
    void GetNext_Print()
    {
    	int i,j;
    	s[0] = '#';
    	len = strlen(s);
    	next[1] = 0;
    	j=0;
    	for(i=2;i<len;i++)
    	{
    		while(j>0 && s[j+1]!=s[i])
    			j = next[j];
    		if(s[j+1] == s[i]){
    			j++;
    		}
    		next[i] = j;
    		//以下是判断是否是循环点
    		int l = i - next[i];
    		if(l == i) continue;
    		if(i%l == 0) //
    			printf("%d %d\n",i,i/l);
    	}
    }
    
    int main()
    {
    	int n,cas = 1;
    	while(scanf("%d",&n)!=EOF && n)
    	{
    		getchar();
    		scanf("%s",s+1);
    		printf("Test case #%d\n",cas++);
    		GetNext_Print();
    		printf("\n");
    	}
    	return 0;
    }

转载于:https://www.cnblogs.com/cykun/archive/2011/02/19/1958661.html