KMP算法求解next数组值(模式串从下标0开始或从下标1开始)以及求值后与主串的匹配过程

  时间:2020-08-03 18:41:40  阅读量:43  评论数:0  作者:祈祷ovo

文章KMP算法求解next数组值(模式串从下标0开始或从下标1开始)以及求值后与主串的匹配过程包含有源码,做相关工作的朋友可以参考源码改下就可以用于项目中去。感谢作者祈祷ovo开源分享。

写在前面:博主是一位普普通通的19届二本大学生,平时最大的爱好就是听听歌,逛逛B站。博主很喜欢的一句话花开堪折直须折,莫待无花空折枝:博主的理解是头一次为人,就应该做自己想做的事,做自己不后悔的事,做自己以后不会留有遗憾的事,做自己觉得有意义的事,不浪费这大好的青春年华。博主写博客目的是记录所学到的知识并方便自己复习,在记录知识的同时获得部分浏览量,得到更多人的认可,满足小小的成就感,同时在写博客的途中结交更多志同道合的朋友,让自己在技术的路上并不孤单。

目录:
1.模式串从下标1开始的next数组求解
       
数据结构严蔚敏版
       
日常算法题版
2.模式串从下标0开始的next数组求解
       
模板1
       
模板2
3.模式串与主串的匹配
       
数据结构严蔚敏版
       
日常算法题版

1.模式串从下标1开始

1.1数据结构严蔚敏版

这个版本是官方标配版,第i个位置的next数组值的意义是:前i-1个字符的最大真公共前后缀的长度加1,加1的目的是下一次主串与模式串失配时模式串要跳到的位置。比如我们一个字符串abab那么它在此处的next数组值为0112;

void get_next(char T[],int next[])
{
	int i=1;
	int j=0;
	next[1]=0;
	while(i<T[0])//T[0]为字符串长度
	{
		if(j==0||T[i]==T[j])//T[i]表示后缀的单个字符,T[j]表示前缀的单个字符  
		{
			i  ;
			j  ;
			next[i]=j; 
		}
		else
		j=next[j];//若字符不相同那么j值回溯 
	} 
}

1.1日常算法题版

有的时候,模式串需要我们手动的输入,我们可以选择从1开始输入字符串,然后求得此模式串的next数组值(注:kmp代表next数组),这个与严蔚敏版不同的是第i个位置的next数组值是前i个字符的最大真公共前后缀长度,比如字符串abab在此段代码中next数组值为0012

   cin>>str 1;//从数组下标为1开始输入
   int len=strlen(str 1);
   int j=0;
   for(int i=2;i<=len;i  )
   {
   	  while(j>0&&str[j 1]!=str[i])
   	  j=kmp[j];
   	  if(str[j 1]==str[i])
   	  j  ;
	  kmp[i]=j; 
   }

2.模式串从下标0开始

2.1模板1

        kmp[0]=0;
        int j=-1;
        for(int i=1;i<needle.length();i  )
        {
            while(j>-1&&needle[j 1]!=needle[i])
            {
                if(j==0)//j==0的时候陷入死循环
                {
                    j=-1;
                    break;
                }
                else
                j=kmp[j]-1;
            }
              if(needle[i]==needle[j 1])
                j  ;
            kmp[i]=j 1;
        }

2.2模板2

        kmp[0] = 0;
        int t;
        for(int i = 1; i < s.length(); i  )
       {
	     t = kmp[i-1];
	     while(t > 0 && s[i] != s[t])
		 t = kmp[t-1];
	     if(s[i] == s[t])
         {
		  t  ;
	      kmp[i] = t;
         }  
           else
           kmp[i]=0;
       } 

3.模式串与主串的匹配

3.1数据结构严蔚敏版

int Index_KMP(String S, String T, int pos){
    // i 用于主串S当前位置下标值,若pos不为1,则从pos位置开始匹配
    int i=pos;
    //j 用于子串T中当前位置下标值
    int j=1;
    // 定义next数组
    int next[255];
    
    // 对串T作分析,得到next数组
    get_next(T,next);
   
    // 若i小于S的长度且j小于T的长度时,循环继续
    while(i<=S[0] && j<=T[0]){
        // 两字母相等则继续,相对于朴素算法增加了
        // j=0 判断
        if(j==0||S[i]==T[j]){
              i;
              j;
        }
        // 指针后退重新开始匹配
        else{
            // j退回合适的位置,i值不变
            j=next[j];
        }
    }
    if(j>T[0]){
        return i-T[0];
    }
    else
        return 0;
}

3.2算法题版(对应模式串从下标0开始的两个模板)

//haystack表示主串
//needle表示模式串
        int i=0;
        j=0;
        int flag;
        while(i<haystack.length())
        {
            flag=0;
            if(haystack[i]==needle[j])
            {
              i  ;
              j  ;
              flag=1;
            }
            else 
            {
                if(j>0)
              {
                j=kmp[j-1];
                flag=1}
            }
            if(j==needle.length())
            return i-needle.length();     
            if(flag==0)
            i  ;
        } 
        return -1;

    }

关键词:kmp算法,算法,求解,next,数组,模式,下标,开始,下标,开始,以及,求值,匹配,过程