KMP入门题 Hdu 1711 2594 3746 HUST 1010 Poj 3461 2752 2406 1961 FZU 1901

骑猪看日落 2021-11-10 23:46 151阅读 0赞

KMP入门题整理，理论学习课参考[ KMP及其next数组性质学习小记 Poj1961 Period - whyorwhnt的专栏][KMP_next_ Poj1961 Period - whyorwhnt]

关于KMP两种next数组的实现方法和区别课参考 [HDU-3746 Cyclic Nacklace - 飘过的小牛][HDU-3746 Cyclic Nacklace -]

**HDU 1711 Number Sequence**

求第二个串在第一个串中第一次出现的位置

#include <cstdio>
    
    const int N=1000005;
    int s[N],t[N/100+10];
    int next[N],len;
    
    void Cal_next (const int *pattern,int len)  //next[]有多个-1
    {
    	int i=0,j=-1;
    	next[0]=-1;
    	while (i<len)
    	{
    		while (j>=0 && pattern[i]!=pattern[j])
    			j=next[j];
    		j++,i++;
    		if (pattern[j]==pattern[i])
    			next[i]=next[j];
    		else
    			next[i]=j;
    	}
    }
    
    int KMP (int sl,int tl)
    {
    	int i=0,j=0;
    	while (i<sl && j<tl)
    		if (j==-1 || s[i]==t[j])
    		{//j == -1 为两个串第一个就没有匹配上
    			i++;
    			j++;
    		}
    		else
    			j=next[j];
    	if (j==tl) return i-j+1;//此为第几个,下标应该是i-j;
    	return -1;
    }
    
    int main ()
    {
    	int T,n,m,i;
    	scanf("%d",&T);
    	while (T--)
    	{
    		scanf("%d%d",&n,&m);
    		for (i=0;i<n;i++)
    			scanf("%d",&s[i]);
    		for (i=0;i<m;i++)
    			scanf("%d",&t[i]);
    		Cal_next (t,n);
    		int ans=KMP(n,m);
    		printf("%d\n",ans);
    	}
    	return 0;
    }

**Poj 3461 Oulipo**  
求第二个串在第一个串中出现的次数

#include <cstdio>
    #include <cstring>
    
    const int N=1000005;
    char s[N],t[N/100+10];
    int next[N],len;
    
    void Cal_next (const char *pattern,int len)  //next[]有多个-1
    {
    	int i=0,j=-1;
    	next[0]=-1;
    	while (i<len)
    	{
    		while (j>=0 && pattern[i]!=pattern[j])
    			j=next[j];
    		j++,i++;
    		if (pattern[j]==pattern[i])
    			next[i]=next[j];
    		else
    			next[i]=j;
    	}
    }
    
    int KMP (int sl,int tl)
    {
    	int i=0,j=0,ans=0;
    	while (i<sl && j<tl)
    	{
    		if (j==-1 || s[i]==t[j])
    		{//j == -1 为两个串第一个就没有匹配上
    			i++;
    			j++;
    		}
    		else
    			j=next[j];
    		if (j==tl)
    		{
    			ans++;
    			j=next[j];
    		}
    	}
    	return ans;
    }
    
    int main ()
    {
    	int T;
    	scanf("%d",&T);
    	while (T--)
    	{
    		scanf("%s",t);
    		scanf("%s",s);
    		Cal_next (t,strlen(t));
    		int ans=KMP(strlen(s),strlen(t));
    		printf("%d\n",ans);
    	}
    	return 0;
    }

**Hdu 2594 Simpsons’ Hidden Talents**  
给你两个字符串s1,s2,让你求一个最大长度的子串t,t是s1的前缀,并且是s2的后缀.  
应用next数组的定义  
s1和s2接起来，求最后一位的后一位的next值(也就是多求一位),如果长度大于两串中任意一串的长度，则输出较小的串长

第一份，2013年写的

#include <cstdio>
    #include <cstring>
    
    const int N=50005;
    char pattern[N*2],str1[N],str2[N];
    int len1,len2;
    int next[N*2];
    
    void Get_next ()
    {	
    	int j=0,k=-1;
    	next[0]=-1;
    	while (pattern[j]!=0)
    		if (k==-1 || pattern[j] == pattern[k])
    		{	
    			j++;
    			k++;
    			next[j]=k;
    		}
    		else k=next[k];
    }
    
    int main ()
    {
    	while (~scanf("%s%s",str1,str2))
    	{
    		len1=strlen(str1);
    		len2=strlen(str2);
    		int len=len1+len2;
    		strcpy(pattern,str1);
    		strcat(pattern,str2);
    		Get_next ();
    		if (next[len] == 0)
    			printf("0\n");
    		else
    		{
    			if (next[len]>len1 || next[len]>len2)       //输出短的那一个
    			{
    				if (len1 > len2)
    					printf("%s %d\n",str2,len2);
    				else
    					printf("%s %d\n",str1,len1);
    			}
    			else
    			{
    				pattern[next[len]]=0;
    				printf("%s %d\n",pattern,next[len]);
    			}
    		}
    	}
    	return 0;
    }

第二份 2014年写的

#include <cstdio>
    #include <cstring>
    #define min(a,b) ((a)<(b)?(a):(b))
    #define max(a,b) ((a)>(b)?(a):(b))
    
    const int N=100005;
    char s[N],t[N];
    int next[N],len;
    
    void Cal_next (const char *pattern,int len)  //next[]有多个-1
    {
    	int i=0,j=-1;
    	next[0]=-1;
    	while (i<len)
    	{
    		while (j>=0 && pattern[i]!=pattern[j])
    			j=next[j];
    		j++,i++;
    		if (pattern[j]==pattern[i])
    			next[i]=next[j];
    		else
    			next[i]=j;
    	}
    }
    
    int main ()
    {
    	while (~scanf("%s%s",s,t))
    	{
    		int len1=strlen(s);
    		int len2=strlen(t);
    		strcat(s,t);
    		Cal_next(s,len1+len2);
    		int ans=min(len1,len2);
    		ans=min(ans,next[len1+len2]);
    		ans=max(ans,0);   //next数组中有可能是-1
    		s[ans]=0;
    		if (ans==0)
    			printf("0\n");
    		else
    			printf("%s %d\n",s,ans);
    	}
    	return 0;
    }
    
    /*
    abcabcabcabc
    abcabcabcabcabc
    abcabc
    abc
    
    12
    3
    */

**HUST 1010 The Minimum Length**

题意：求给出的字符串的最小循环节。

#include <cstdio>
    #include <cstring>
    
    const int N=1000005;
    char pattern[N];
    int next[N],len;
    
    void Get_next ()  //next[]只有第一个是-1
    {
    	int j=0,k=-1;
    	next[0]=-1;
    	while (pattern[j])
    		if (k==-1 || pattern[j] == pattern[k])
    		{
    			j++;
    			k++;
    			next[j]=k;
    		}
    		else k=next[k];
    }
    
    int main ()
    {
    	while (~scanf("%s",pattern))
    	{
    		Get_next ();
    		int len=strlen(pattern);
    		int temp=len-next[len];
    		printf("%d\n",temp);
    	}
    	return 0;
    }

**Poj 2752 Seek the Name, Seek the Fame**

题意：求出字符串S所有子串的长度，该子串满足即是S的前缀又是S的后缀。

思路：利用KMP的NEXT数组的特性，Next\[pos\]的含义是在pos处失配时pos应该指向的下一个位置，那么0-(Next\[pos\]-1)构成的字符串和(pos-Next\[pos\])-(pos-1)构成的字符串是相同的，即0-(Next\[pos\]-1)构成的字符串是，0-pos-1构成的字符串的前缀后缀子串。从S末尾开始不断递归式处理。

网上有张图不错，摘自：http://hi.baidu.com/aekdycoin/item/c8818f4b13db26e51381dad4

![SouthEast][]

非递归实现

#include <cstdio>
    #include <cstring>
    
    const int N=400005;
    char s[N],t[N];
    int next[N],data[N];
    
    void Get_next (char pattern[])  //next[]只有第一个是-1
    {
    	int j=0,k=-1;
    	next[0]=-1;
    	while (pattern[j])
    		if (k==-1 || pattern[j] == pattern[k])
    			next[++j]=++k;
    		else k=next[k];
    }
    
    int main ()
    {
    	while (~scanf("%s",s))
    	{
    		int len=strlen(s);
    		Get_next(s);
    		memset(data,0,sizeof(data));
    		int k=len,cnt=0;
    		while (k!=0)
    		{
    			data[cnt++]=k;
    			k=next[k];
    		}
    		if (cnt==0)
    			printf("0\n");
    		else
    		{
    			cnt--;
    			while (cnt>0)
    				printf("%d ",data[cnt--]);
    			printf("%d\n",data[cnt]);
    		}
    	}
    	return 0;
    }

递归实现

#include <cstdio>
    #include <cstring>
    
    const int NUM=400010;
    char pattern[NUM];
    int next[NUM],len;
    
    void Get_next ()
    {	
    	int j=0,k=-1;
    	next[0]=-1;
    	while (pattern[j])
    		if (k==-1 || pattern[j] == pattern[k])
    		{	
    			j++;
    			k++;
    			next[j]=k;
    		}
    		else k=next[k];
    }
    
    void Output (int loc)
    {
    	if (next[loc]!=0)
    		Output (next[loc]);
    	printf("%d ",loc);
    }
    
    int main()
    {
    	while(scanf("%s",pattern) != EOF)
    	{
    		Get_next ();
    		len = strlen (pattern);
    		Output (len);
    		printf("\n");
    	}
    	return 0;
    }

**Poj 2406 Power Strings**

题意:给出一个字符串,将其分解为若干子串的和,求可分解的最多子串的个数  
给你一个长度为n的字符串,首先我们找到这样一个字符串,这个字符串满足长度为n的字符串是由这个字符串重复叠加得到并且这个字符串的长度要最小.然后输出重复的次数

#include <cstdio>
    #include <cstring>
    
    const int N=1000005;
    char pattern[N];
    int next[N],len;
    
    void Get_next ()  //next[]只有第一个是-1
    {
    	int j=0,k=-1;
    	next[0]=-1;
    	while (pattern[j])
    		if (k==-1 || pattern[j] == pattern[k])
    			next[++j]=++k;
    		else k=next[k];
    }
    
    void Cal_next (const char *pattern,int len)  //改进写法,next[]有多个-1
    {
    	int i=0,j=-1;
    	next[0]=-1;
    	while (i<len)
    	{
    		while (j>=0 && pattern[i]!=pattern[j])
    			j=next[j];
    		j++,i++;
    		if (pattern[j]==pattern[i])
    			next[i]=next[j];
    		else
    			next[i]=j;
    	}
    }
    
    int main ()
    {
    	int Cas=1;
    	while (scanf("%s",pattern) && pattern[0]!='.')
    	{
    		Cal_next (pattern,strlen(pattern));
    		int len=strlen(pattern);
    		int temp=len-next[len];
    		if (len%temp==0)
    			printf("%d\n",len/temp);
    		else
    			printf("1\n");
    	}
    	return 0;
    }

**Poj 1961 Period**  
给若干个字符串,判断该字符串的前n位是由一个串最多重复了几次得到的.  
比如,给ababab,结果是前4位重复了2次，前6位重复了3次,忽略重复一次的情况.

#include <cstdio>
    
    const int N=1000005;
    char pattern[N];
    int next[N],len;
    
    void Get_next ()  //next[]只有第一个是-1
    {
    	int j=0,k=-1;
    	next[0]=-1;
    	while (pattern[j])
    		if (k==-1 || pattern[j] == pattern[k])
    			next[++j]=++k;
    		else k=next[k];
    }
    
    void Deal ()
    {
    	Get_next ();
    	for (int i=2;i<=len;i++)
    	{
    		int n=i-next[i];
    		if (i%n==0 && i/n>1)
    			printf("%d %d\n",i,i/n);
    	}
    	printf("\n");
    }
    
    int main ()
    {
    	int Cas=1;
    	while (scanf("%d",&len) && len)
    	{
    		scanf("%s",pattern);
    		printf("Test case #%d\n",Cas++);
    		Deal ();
    	}
    	return 0;
    }

**Hdu 3746 Cyclic Nacklace**  
在一个串的后面添加若干字符，使其成为一个循环串,循环次数至少为2  
结论：当且仅当len%(len-next\[len\])==0时,s\[next\[len-1\]~len-1\]为最小循环节

#include <cstdio>
    #include <cstring>
    
    const int N=100005;
    char pattern[N];
    int next[N],len;
    
    void Get_next ()  //next[]只有第一个是-1
    {  
    	int j=0,k=-1;
    	next[0]=-1;
    	while (pattern[j])
    		if (k==-1 || pattern[j] == pattern[k])
    			next[++j]=++k;
    		else k=next[k];
    }
    
    int main ()
    {
    	int T;
    	scanf("%d",&T);
    	while (T--)
    	{
    		scanf("%s",pattern);
    		Get_next ();
    		len=strlen(pattern);
    		int c = len - next[len];  //循环节的长度  
    		if (len!=c && len%c==0) //循环多次
    			printf("0\n");  
    		else  
    		{  
    			int add=c-next[len]%c; //%去掉完整循环的部分
    			printf("%d\n",add);  
    		}
    	}
    	return 0;
    }

**FZU 1901 Period II**

题意：找到所有满足S\[i\]=S\[i+P\] for i in \[0..SIZE(S)-p-1\]的前缀，并且长度为p  
注意字符串本身就符合要求

#include <cstdio>
    #include <cstring>
    
    const int N = 1000005;
    
    char str[N];
    int next[N],ans[N];
    
    void Get_next (char *pattern)
    {     
        int j=0,k=-1;
        next[0]=-1;
        while (pattern[j]!=0)  
            if (k==-1 || pattern[j] == pattern[k])  
                next[++j]=++k;  
            else k=next[k];
    } 
    
    int main ()
    {
        int T;
        scanf("%d",&T);
        for (int Cas=1;Cas<=T;Cas++)
        {
    		int cnt=0;
    		scanf("%s",str);
    		int len = strlen(str);
    		Get_next(str);
    		int tmp = next[len];
    		while (tmp!=0)
    		{
    			ans[cnt++] = len-tmp;
    			tmp = next[tmp];
    		}
    		ans[cnt++]=len;
    		printf("Case #%d: %d\n",Cas,cnt);
    		for (int i=0;i<cnt;i++)
    			printf(i==cnt-1?"%d\n":"%d ",ans[i]);
    	}
    	return 0;
    }

[KMP_next_ Poj1961 Period - whyorwhnt]: http://blog.csdn.net/whyorwhnt/article/details/8883074
[HDU-3746 Cyclic Nacklace -]: http://blog.csdn.net/niushuai666/article/details/6965517
[SouthEast]: /images/20211109/916771ecd4d14abaa5e8b44b231afe44.png