kmp1-HDU1711 HDU1686 HDU2087 HDU3746

HDU 1711 kmp模板题

http://acm.hdu.edu.cn/showproblem.php?pid=1711

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #define N 1000005
     
    
   

    

     

    
    

     

      int s[N];
     
    
   

    

     

    
    

     

      int p[N];
     
    
   

    

     

    
    

     

      int next[N];
     
    
   

    

     

    
    

     

      int m,n;
     
    
   

    

     

    
    

     

      void getnext(){
     
    
   

    

     

    
    

     
 int j=0,k=-1;
     
    
   

    

     

    
    

     

       next[0]=-1;
     
    
   

    

     

    
    

     
 while(j<m){
     
    
   

    

     

    
    

     
 if(k==-1||p[j]==p[k]){
     
    
   

    

     

    
    

     

       j++;
     
    
   

    

     

    
    

     

       k++;
     
    
   

    

     

    
    

     

       next[j]=k;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       k=next[k];
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int kmp(){
     
    
   

    

     

    
    

     
 int i=0,j=0;
     
    
   

    

     

    
    

     

       getnext();
     
    
   

    

     

    
    

     
 while(i<n){
     
    
   

    

     

    
    

     
 if(j==-1||s[i]==p[j]){
     
    
   

    

     

    
    

     

       i++;
     
    
   

    

     

    
    

     

       j++;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       j=next[j];
     
    
   

    

     

    
    

     
 if(j==m)
     
    
   

    

     

    
    

     
 return i;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return -1;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main(){
     
    
   

    

     

    
    

     
 int t;
     
    
   

    

     

    
    

     
 scanf("%d",&t);
     
    
   

    

     

    
    

     
 while(t--){
     
    
   

    

     

    
    

     
 scanf("%d%d",&n,&m);
     
    
   

    

     

    
    

     
 for(int i=0;i<n;i++)
     
    
   

    

     

    
    

     
 scanf("%d",&s[i]);
     
    
   

    

     

    
    

     
 for(int i=0;i<m;i++)
     
    
   

    

     

    
    

     
 scanf("%d",&p[i]);
     
    
   

    

     

    
    

     
 if(kmp()==-1)
     
    
   

    

     

    
    

     
 printf("-1\n");
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     
 printf("%d\n",kmp()-m+1);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

HDU1686

http://acm.hdu.edu.cn/showproblem.php?pid=1686

题意就是，给你一个字符串A，一个字符串B，求A在B中总共出现了几次，注意，重复的也算。

稍微改动即可。

HDU 2087 剪花布条(KMP:贪心)

http://acm.hdu.edu.cn/showproblem.php?pid=2087

直接用KMP算法,用T模式串去匹配S主串即可，但是当匹配成功的时候要看看当前匹配点离上一个匹配点是不是距离差>=T的长度。

贪心，从左向右依次选取即可，证明略。

  

   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      #include<cmath>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      const int MAXN=1000+100;
     
    
   

    

     

    
    

     

      char S[MAXN],T[MAXN];
     
    
   

    

     

    
    

     

      int next[MAXN];
     
    
   

    

     

    
    

     

      int n,m;
     
    
   

    

     

    
    

     

      int cnt,last;
     
    
   

    

     

    
    

     

      void getFail()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       next[0]=next[1]=0;
     
    
   

    

     

    
    

     
 for(int i=1;i<m;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int j=next[i];
     
    
   

    

     

    
    

     
 while(j && T[i]!=T[j]) j=next[j];
     
    
   

    

     

    
    

     

       next[i+1] = (T[i]==T[j])?j+1:0;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void KMP()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       n=strlen(S);
     
    
   

    

     

    
    

     

       m=strlen(T);
     
    
   

    

     

    
    

     

       getFail();
     
    
   

    

     

    
    

     
 int j=0;
     
    
   

    

     

    
    

     
 for(int i=0;i<n;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 while(j && S[i]!=T[j]) j=next[j];
     
    
   

    

     

    
    

     
 if(S[i]==T[j]) j++;
     
    
   

    

     

    
    

     
 if(j==m)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(cnt==0)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       cnt++;
     
    
   

    

     

    
    

     

       last=i;//last指向匹配位置的末尾
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else if(i-last>=m)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       cnt++;
     
    
   

    

     

    
    

     

       last=i;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 while(scanf("%s",S)==1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(strcmp(S,"#")==0)
     
    
   

    

     

    
    

     
 break;
     
    
   

    

     

    
    

     
 scanf("%s",T);
     
    
   

    

     

    
    

     

       cnt=0;
     
    
   

    

     

    
    

     

       KMP();
     
    
   

    

     

    
    

     
 printf("%d\n",cnt);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

 HDU3746 next应用

http://acm.hdu.edu.cn/showproblem.php?pid=3746

逻辑就是找到最长相同前后缀再在后面加上那一段就找到了.

注意：用原始next，next数组存的是前缀和后缀的最大匹配值，

比如abcabca

改进前最后一个字符next[7]=4,表示的是前缀和后缀最大匹配是4，即abca和abca。

改进后的next[7]=-1。

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      #define N 100010
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      char s[N];
     
    
   

    

     

    
    

     

      int nextval[N];
     
    
   

    

     

    
    

     

      int len;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void getnext(const char *s)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int i = 0, j = -1;
     
    
   

    

     

    
    

     

      	nextval[0] = -1;
     
    
   

    

     

    
    

     
	while(i != len)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		if(j == -1 || s[i] == s[j])
     
    
   

    

     

    
    

     

      			nextval[++i] = ++j;
     
    
   

    

     

    
    

     
		else
     
    
   

    

     

    
    

     

      			j = nextval[j];
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int ncase;
     
    
   

    

     

    
    

     
	int length, add;
     
    
   

    

     

    
    

     
	scanf("%d", &ncase);
     
    
   

    

     

    
    

     
	while(ncase--)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		scanf("%s", s);
     
    
   

    

     

    
    

     

      		len = strlen(s);
     
    
   

    

     

    
    

     

      		getnext(s);
     
    
   

    

     

    
    

     
		/*for(int i = 0; i <= len; ++i) //查看next数组的内容
     
    
   

    

     

    
    

     

       cout<<nextval[i]<<" ";
     
    
   

    

     

    
    

     

       cout<<endl;*/
     
    
   

    

     

    
    

     

      		length = len - nextval[len]; //循环节的长度
     
    
   

    

     

    
    

     
		if(len != length && len % length == 0) //循环多次
     
    
   

    

     

    
    

     
			printf("0\n");
     
    
   

    

     

    
    

     
		else
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			add = length - nextval[len] % length; //取余的作用：abcab，去掉abc
     
    
   

    

     

    
    

     
			printf("%d\n",add);
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/82492660