精华内容
下载资源
问答
  • KMP算法源代码 C语言

    2017-04-26 20:46:03
    KMP算法源代码 C语言 KMP算法源代码 C语言 KMP C语言
  • Kmp算法C语言简单实现

    千次阅读 多人点赞 2019-06-01 09:54:06
    前言: 菜鸟一枚,最近学习了Kmp算法,其中有很多的不懂,在这里总结一下前两天学习的结果,写出来最简单的C语言代码实现算法,其中有不少借鉴到别处,如有侵权,请联系我,我定反思并道歉。 好了,言归正传,在这...

    前言: 菜鸟一枚,最近学习了Kmp算法,其中有很多的不懂,在这里总结一下前两天学习的结果,写出来最简单的C语言代码实现算法,其中有不少借鉴到别处,如有侵权,请联系我,我定反思并道歉。

    好了,言归正传,在这两天学习kmp算法的过程中,最让我感到头痛的就是构造next数组了,我觉得只要构造好了该数组,就算是成功了一半。在计算next值得时候,最重要的是理解最大前缀后缀,在计算出最大长度值后再计算next会轻松很多,当然很多的说法我觉得都是殊途同归,最终都是为了next表。

    下面根据具体代码和注释来解释:

    /*next数组*/
    void GetNext(sq q, int next[])
    {
    	int i = 0,j = -1;
    	next[0] = -1;      //next数组默认首值为-1
    	while (i < q.length)
    	{
    	/*自匹配过程*/
    		if (j == -1 || q.string[i] == q.string[j])  //如果是首字符或者两个字符相等,继续下一个字符比较
    		{
    			i++;
    			j++;
    			next[i] = j;
    		}
    		else
    			j = next[j];  //找相对较小的最大前后缀
    	}
    
    		for (i = 0; i < q.length; i++)
    		{
    			printf("%2d", next[i]);  
    
    		}
    	
    }
    

    next数组的实现代码就如同上述,具体的原理比较复杂,我不太解释的清楚,推荐大家搜索CSDN上面的大佬博客,有很多都讲的比较清楚(前辈可敬啊)。

    接下来,利用上面的next数组进行Kmp字符串的匹配:

     /*Kmp算法*/
    	int Kmp(sq s,sq p,int next[])
    	{
    		int c = 0;     //主串移动变量
    		int d = 0;     //模式串移动变量
    		while (c < s.length && d < p.length)       //合法长度之内
    		{
    			if(d == -1||s.string[c]==p.string[d]) //d== -1代表是模式串首字符
    				{
    				/*d==-1或者匹配成功就累加继续比较下一个*/
    					c++;
    					d++;
    				}
    			else
    				d = next[d];                     //利用Next数组进行移动,这里是移动较大的长度,避免了不必要的回溯
    
    		}
    
    		if (d == p.length)
    			return c - p.length;     //只要能匹配成功,最后d都会累加到模式串的长度
    		else
    			return -1;               //没有匹配成功
    	}
    

    我们可以看见,Kmp算法的核心就是next数组,这里就是根据已经计算好的next数组进行移动比较,避免了蛮力算法的一个一个回溯,减小了时间复杂度。

    下面贴出完整程序:

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    #define N 100
    
    /*串结构体*/
    typedef struct Stirngs
    {
    	char string[100];
    	int length;
    }sq;
    
    
    /*next数组*/
    void GetNext(sq q, int next[])
    {
    	int i = 0,j = -1;
    	next[0] = -1;
    	while (i < q.length)
    	{
    		if (j == -1 || q.string[i] == q.string[j])
    		{
    			i++;
    			j++;
    			next[i] = j;
    		}
    		else
    			j = next[j];
    	}
    
    		for (i = 0; i < q.length; i++)
    		{
    			printf("%2d", next[i]);
    
    		}
    	
    }
     /*Kmp算法*/
    	int Kmp(sq s,sq p,int next[])
    	{
    		int c = 0;
    		int d = 0;
    		while (c < s.length && d < p.length)       //合法长度之内
    		{
    			if(d == -1||s.string[c]==p.string[d]) //d== -1代表是首字符;
    				{
    					c++;
    					d++;
    				}
    			else
    				d = next[d];                     //利用Next数组进行移动
    
    		}
    
    		if (d == p.length)
    			return c - p.length;
    		else
    			return -1;
    	}
    
    	/*主函数*/
    	int main(void)
    	{
    		int next[N];
    		int a;
    		sq s ;
    		sq p ;
    		printf("Please Input S string: \n");
    		scanf("%s", s.string);
    		printf("Please Input P string: \n");
    		scanf("%s", p.string);
    		s.length = strlen(s.string);
    		p.length = strlen(p.string);
    		GetNext(p,next);
    		printf("\n");
    		if (Kmp(s, p, next)!= -1)
    		{
    			printf("kmp匹配成功!");
    			for (a = Kmp(s, p, next); a < Kmp(s, p, next) + p.length; a++)
    			{
    				printf("%c", s.string[a]);
    			}
    		}
    		else
    			printf("匹配失败!");
    
    		printf("\n");
    		system("pause");
    		return 0;
    	}
    
    

    运行的结果:
    可以看出计算的next数组和在主串中匹配后打印的字符串是对应的
    在这里插入图片描述

    到这里,我目前所学的Kmp算法就是这样,欢迎大家之处我的错误,因为是小白,所以可能很多低级错误,恳请大家不要见笑,多多包涵。

    展开全文
  • KMP算法用于判断一个字符串是否包含另一个字符串,如果包含就返回脚标。其实KMP算法本身特别简单,我看了几篇本章都号称简单易懂,结果看得我云里雾里,直到我看到了阮一峰:字符串匹配的KMP算法,才真正看懂。下文...

            KMP算法用于判断一个字符串是否包含另一个字符串,如果包含就返回脚标。其实KMP算法本身特别简单,我看了几篇本章都号称简单易懂,结果看得我云里雾里,直到我看到了阮一峰:字符串匹配的KMP算法,才真正看懂。下文的第一部分基本上都是阮一峰文章的转述,第二部分代码也是在网上其他地方找的。第三部分KMP算法的理解,才是笔者的东西,相信看了第三部分你会豁然开朗。

    一、KMS算法的处理过程

    下面用 KMP算法在字符串"BBC ABCDAB ABCDABCDABDE"中寻找字符串"ABCDABD":

    首先,字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符,进行比较。因为B与A不匹配,所以搜索词后移一位。

    因为B与A不匹配,搜索词再往后移。

    就这样,直到字符串有一个字符,与搜索词的第一个字符相同为止。

    接着比较字符串和搜索词的下一个字符,还是相同。

    直到字符串有一个字符,与搜索词对应的字符不相同为止。

    这时,最自然的反应是,将搜索词整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把"搜索位置"移到已经比较过的位置,重比一遍。

    一个基本事实是,当空格与D不匹配时,你其实知道前面六个字符是"ABCDAB"。KMP 算法的想法是,设法利用这个已知信息,不要把"搜索位置"移回已经比较过的位置,继续把它向后移,这样就提高了效率。

    怎么做到这一点呢?可以针对搜索词,算出一张《部分匹配表》(Partial Match Table)。这张表是如何产生的,后面再介绍,这里只要会用就可以了。

        已知空格与D不匹配时,前面六个字符"ABCDAB"是匹配的。查表可知,最后一个匹配字符B对应的"部分匹配值"为2,因此按照下面的公式算出向后移动的位数:

        移动位数 = 已匹配的字符数 - 对应的部分匹配值

        因为 6 - 2 等于4,所以将搜索词向后移动 4 位。

    移动完后,再比较,发现空格与C还是不匹配,于是搜索词还要继续往后移。这时,已匹配的字符数为2("AB"),对应的"部分匹配值"为0。所以,移动位数 = 2 - 0,结果为 2,于是将搜索词向后移 2 位。

    这时空格与A还是不匹配,继续后移一位。(因为搜索词已经移动到头了,所以默认的移动距离为1位)

    这个时候发现能匹配了,于是又逐位比较,直到发现C与D不匹配。于是,移动位数 = 6 - 2,继续将搜索词向后移动 4 位。

    这下就完全匹配了。

    下面介绍《部分匹配表》是如何产生的。

      首先,要了解两个概念:"前缀"和"后缀"。 "前缀"指除了最后一个字符以外,一个字符串的全部头部组合;"后缀"指除了第一个字符以外,一个字符串的全部尾部组合。

            比如“bread”这个字符串的前缀是除了最后一个字符“d”,还剩下"brea",它的全部组合字符串有:"b"、"br"、"bre"、"brea"。

            “bread”这个字符串的后缀是除了第一个字符“b”,还剩下"read",它的全部组合字符串有:"r"、"re"、"rea"、"read"。

            "部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例,

    -"A"的前缀和后缀都为空集,共有元素的长度为0;

    -"AB"的前缀为[A],后缀为[B],共有元素的长度为0;

    -"ABC"的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;

    -"ABCD"的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;

    -"ABCDA"的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为"A",长度为1;

    -"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为"AB",长度为2;

    -"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。

             "部分匹配值"其实还可以定义为:把字符串沿着中间的字符折叠,字符串首尾重叠的字符个数。

            比如“ABC”沿着字符“B”折叠,首尾的“A”和“C”就不能重叠,所以"部分匹配值"为0.

            "ABCDA"沿着字符“C”折叠,首尾的“A”能重叠,所以"部分匹配值"为1.

            "ABCDAB"沿着字符“C”和“D”的中间折叠,首尾的“AB”能重叠,所以"部分匹配值"为2.

    二、C语言程序

            利用上面KMS的处理过程和部分匹配值的生成方法,就可以写程序了:

    void cal_next(char *str, int *next, int len)
    {
        next[0] = -1;//next[0]初始化为-1,-1表示不存在相同的最大前缀和最大后缀
        int k = -1;//k初始化为-1
        for (int q = 1; q <= len-1; q++)
        {
            while (k > -1 && str[k + 1] != str[q])//如果下一个不同,那么k就变成next[k],注意next[k]是小于k的,无论k取任何值。
            {
                k = next[k];//往前回溯
            }
            if (str[k + 1] == str[q])//如果相同,k++
            {
                k = k + 1;
            }
            next[q] = k;//这个是把算的k的值(就是相同的最大前缀和最大后缀长)赋给next[q]
        }
    }
    
    int KMP(char *str, int slen, char *ptr, int plen)
    {
        int *next = new int[plen];
        cal_next(ptr, next, plen);//计算next数组
        int k = -1;
        for (int i = 0; i < slen; i++)
        {
            while (k >-1&& ptr[k + 1] != str[i])//ptr和str不匹配,且k>-1(表示ptr和str有部分匹配)
                k = next[k];//往前回溯
            if (ptr[k + 1] == str[i])
                k = k + 1;
            if (k == plen-1)//说明k移动到ptr的最末端
            {
                //cout << "在位置" << i-plen+1<< endl;
                //k = -1;//重新初始化,寻找下一个
                //i = i - plen + 1;//i定位到该位置,外层for循环i++可以继续找下一个(这里默认存在两个匹配字符串可以部分重叠),感谢评论中同学指出错误。
                return i-plen+1;//返回相应的位置
            }
        }
        return -1;  
    }
    
    

    测试程序:

        char *str = "bacbababadababacambabacaddababacasdsd";
        char *ptr = "ababaca";
        int a = KMP(str, 36, ptr, 7);
        return 0;

    三、KMS的理解

    当搜索词已经匹配了6个字符,最后一个字符不匹配时

    传统的做法是移动一位,然后重新比较

    可是KMS却是直接移动了6 - 2 =4位:

    这是为什么呢?

    怎么保证的移动1位、移动2位、移动3位时遇到的字符串都不匹配,所以KMS能直接移动4位,再去比较呢?

    其实非常简单,这就是字符串沿中间折叠后,首尾字符重叠个数(也就是部分匹配值)的作用所在。

    下面我举个例子就懂了:

    比如要在字符串“123456789”中找“4568”

    当匹配到上图的位置时,发现字符“7”和字符“8”不匹配,于是传统的方法是向后移动一位:

    而KMS的移动距离用公式计算为:3-0=3位

    KMS算法把“4568”中已经匹配过的“456”,直接跳过去了。为什么这里能直接把匹配过的字符串“456“跳过去呢?

    下面我们来讨论,我们把已经匹配过的字符分5种情况:(以3个字符来举例)

    1)、已经匹配过的字符串中,每个字符都不相同,如”456“

        如果是这种情况,毫无疑问是可以直接把已匹配的字符跳过去的。

    2)、已经匹配过的字符串中,每个字符都相同,如”444“

        这种情况,最多只能移动1位,比如下面的例子:

    3)、已经匹配过的字符串中,首尾字符相同,如”454“

        这种情况,移动位数要大于1,小于等于2。比如:

    移动一位后:

    首字符会和中间的字符对齐,他们不相同。再移动一位,就可能完全匹配了,因此移动位数最多为2。

    4)、已经匹配过的字符串中,首两个字符相同,如”445“

    移动一位:

    最后两个字符会和首两个字符对齐,他们一定不相同。

    移动两位:

    最后一个字符会和首字符对齐,他们一定不相同。因此移动位数最少为3。

    5)、已经匹配过的字符串中,尾两个字符相同,如”455“

    同理,移动位数最少为3。

            

            经过上面的例子分析,可以看出KMS算法就是对已经匹配过的字符串再次利用来提高效率的。

            KMS算法可以一句话总结为:已经匹配过的字符串如果首尾有相同的字母,就要少移动相应的位数,否则,已经匹配了多少个字符,就可以移动多少位。

    展开全文
  • KMP算法C语言实现

    2013-07-27 11:57:01
    C语言开发的KMP算法
  • KMP算法C语言代码实现

    千次阅读 2017-11-19 22:20:41
    KMP算法C语言代码实现 // //核心思想:匹配过程中匹配不等时,不需回溯i指针,而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离继续比较。 //**************************************...

        KMP算法的C语言代码实现
    //
    //核心思想:匹配过程中匹配不等时,不需回溯i指针,而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离继续比较。
    //******************************************************************************************************************************

    #include <stdio.h>
     
    #include <string.h>
    int index_KMP(char *s,char *t,int pos); 
    //利用模式串的t的next函数求t在主串s中的第pos个位置之后的位置的KMP算法(t非空,1<=pos<=Strlength(s))。
    void get_next(char * t,int * next); 
    //求模式串t的next函数的并存入数组next[]中。
    char s[20]="adjfskjfskdjsfkglsi";
    char t[5]="skdj";
    int next[5];
    int pos=0;
    void main()
    { 
           int n; 
           get_next(t,next);
           n=index_KMP(s,t,pos);
           if(n!=0)
           printf("\n模式串 t 在主串 s 中第 %d 个位置之后。\n\n",n); 
          else
          printf("\n主串中不存在与模式串相匹配的子串!\n\n");
    }
    int index_KMP(char *s,char *t,int pos) 
    //利用模式串的T的NEXT函数求t在主串s中的第pos个位置之后的位置的KMP算法,(t非空,1<=pos<=Strlength(s)).
    { 
          int i=pos,j=1;
         while (i<=(int)strlen(s)&&j<=(int)strlen(t))
         { 
                 if (j==0  ||  s[i]==t[j-1]) //继续进行后续字符串的比较
                 {      
                     i++; 
                     j++; 
                 }
                else j=next[j]; //模式串向右移动
       }
      if (j>(int)strlen(t)) //匹配成功
      return i-strlen(t)+1;
     else //匹配不成功 
     return 0; 
    }
    void get_next(char *t,int *next) 
    //求模式串t的next函数的并存入数组next[]中。
    {
          int i=1,j=0;
          next[0]=next[1]=0;
          while (i<(int)strlen(t)) 
          { 
                 if (j==0 || t[i]==t[j]) 
                 { 
                      i++; 
                      j++; 
                      next[i]=j; 
                 } 
          else j=next[j];
        }
    }




    /**//*
    NO.1
    O(n^2)的算法:
    */

    /**//*枚举主串的每一个位置开始比较*/

    #include <stdio.h>
    
    #define MAX 101
    
    int main(void)
    ...{
        char a[MAX],b[MAX];
        int la=0,lb=0,i,j,k ;
        char c  ;
         
        while ( (c =getchar())!= ' ')
        a[++la] = c ;
        while ( (c =getchar())!= ' ')
        b[++lb] = c ;
        
        for(i=1 ; i<=la ; i++)
        ...{
                for(j=1,k=i; j<= lb && (b[j] == a[k]) ; j++,k++) ;
                if ( j > lb )
                break ;
        }
        
        if ( j > lb)
        printf("No.%d ",i);
        else
        printf("No Soulation!!! ");
                 
                
        
        system("pause");   
        return 0 ;
    }



    /**/ /*
    No.2  O(a+b) 的算法:该算法是由knuth 等三个人想出来的,简称为:KMP 算法
    基本思想是:
    一般的算法为什么这么低效呢?那是因为主串指针回溯情况过多:
    主串指针如果不回溯的话,速度就会加快,那我们就会想:
    如何让主串指针不回溯?
    KMP算法就是解决了这个问题,所以速度变得更快速了
    它是这样子的:
    用一个数组:next[] 求得失配时的位置,然后保存下来,具体请看如下程序:

    */

    */

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAX 101
    
    
    void get_next( int *next,char *a,int la) /**//*求NEXT[]的值*/
    ...{
         int i=1,j=0 ;
         next[1] = 0 ;
         
         while ( i <= la) /**//*核心部分*/
         ...{
               if( a[i] == a[j] || j == 0 )
               ...{
                   j ++ ;
                   i ++ ;
                   if( a[i] == a[j])
                   next[i] = next[j];
                   else
                   next[i] = j ;
               }
               else
               j = next[j] ;
         }
    }
    
    int  str_kmp( int *next, char *A ,char *a, int lA,int la)/**//* EASY*/
    ...{
         int i,j,k ;
         i = 1 ;
         j = 1 ;
         while ( i<=lA && j <= la )
         ...{
               if(A[i] == a[j] ||  j == 0 )
               ...{
                       i ++ ;
                       j ++ ;
               }
               else
               j = next[j] ;
         }
         
         if ( j> la)
         return i-j+1 ;
         else
         return -1 ;
    }
    
    int main(void)
    ...{
        int n,k;
        int next[MAX]=...{0} ;
        int lA=0,la =0 ;
        char A[MAX],a[MAX] ;
        scanf("%s %s",A,a) ;
        
        lA = strlen(A);
        la = strlen(a);
        for(k=la-1; k>= 0 ;k --)
        a[k+1] = a[k] ;
        for(k=lA-1; k>= 0 ;k --)
        A[k+1] = A[k] ;
        
        get_next(next,a,la) ;
        k = str_kmp(next,A,a,lA,la);
        if ( -1 == k)
        printf("Not Soulation!!! ");
        else
        printf("%d ",k) ;
        system("pause");
        
        return 0 ;
    }



    下面这个一般的回溯算法验证可以使用:

    子串的匹配是一个很常见的问题,意思就是说在一个给定的大字符串中寻找给定的子字符串。这是一个很经典的问题,包括一代宗师D.Knuth都在这个问题上有很深入的研究,并提出了所谓的KMP算法。当然这个问题的一个最直观的算法就是这里给出的回溯法。

    回溯法求解子串的过程为:依次遍历大字符串和子串,当发现不相等的时候就回溯到上次起始字符的下一个字符继续,并给子串起始位置清零。当遍历完整个大字符串(没有找到)或者遍历完子串(找到)则算法退出。

    实现源码为:

    int FindSubString(const char* src,const char* sub)
    {
           int srcl = strlen(src);
           int subl = strlen(sub);
    < xmlnamespace prefix ="o" ns ="urn:schemas-microsoft-com:office:office" /> 
           if (subl > srcl)
                  return -1;
     
           int i = 0;
           int j = 0;
     
           while ((i < srcl) && (j < subl))
           {
                  if (src[i] == sub[j])
                  {
                         i++;
                         j++;
                  }
                  else
                  {
                         i = i - j + 1;  //回溯,位置确定请根据已遍历字符串长度为基点计算
                         j = 0;
                  }
           }
     
           if (j >= subl)
           {
                  return i - subl;
           }
          
           return -1;
     
    }


    展开全文
  • KMP算法c语言实现)

    2021-04-18 08:52:35
    挨个遍历的算法是一种低效的,于是三位前辈,D.E.Kunth, J.H.Morris, V.R.Pratt发表乐一个模式匹配算法,可以大大避免重复遍历的情况,我们把它称之为克努特——莫里斯——普拉斯算法,简称KMP算法。 一、什么是...

    前言

    我们在对比字符串时若发现有一个字符不满足,则从下一个字符重新匹配,挨个遍历的算法是一种低效的,于是三位前辈,D.E.Kunth, J.H.Morris, V.R.Pratt发表了一个模式匹配算法,可以大大避免重复遍历的情况,我们把它称之为克努特——莫里斯——普拉斯算法,简称KMP算法。


    一、KMP模式匹配算法原理

    在这里插入图片描述

    我们不直接讲代码,我们先理解一下他为什么比朴素算法好,按照我们上面说的朴素算法进行匹配,此时前五个字母,两个串完全相等,直到第六个字母,c和d不相等,接下来按照朴素算法应该从第一个串的第二个对比,不相等,再到第三个对比,直到第四个字母a和下面串的a相等,这样从主串一步步移动,似乎没什么问题,但是我们仔细观察发现字串a与他后面的b,c都不相同,而在我们第一次匹配时,主串的前五位和子串的前五位相同,那么字串的a肯定和主串二三位置的b,c不等,所以我们将主串移动到第二个位置,和第三个位置的操作是多余的。所以我们应该直接忽略这两个操作,直接将主串挪到第四个位置a的位置开始进行匹配,从这里我们可以分析得到在字符串对比中有些回溯是可以不用发生的——所谓好马不吃回头草,我们的kmp算法就是为了让不必要的回溯不发生而诞生的。

    二、KMP算法的具体操作

    1.回溯的步数

    上文我们提到了若两个字符不相等时,主串会回溯,我们的KMP算法可以不让主串进行回溯,我们是通过移动子串继续匹配的,如上图所示,我们利用kmp算法可以将字串移到主串的第四个位置进行比对,假设字串的位置由j表示,此时我们也就是移到了j = 3的位置继续和主串的“c”进行比较,既然我们是移动子串,那么这个回溯步数就和子串有特定的联系,这里引入一个概念,字串的前后缀,例如“abc”,它的前缀有“a“,”ab“,后缀有”c”,“bc”,我们回溯的步数是根据字串的前后缀相似度,也就是最长相等前后缀,例如“abcabd”我们的j = 6(j为字串的字母位置)时,发现d与主串的c不等,需要移动,这个最长前后缀是在d之前的“abcab”中寻找的,我们可以很容易得到最长前后缀为“ab”,所以我们移到了j = 3的位置,也就是str【2】,综上我们每一个位置的字母都有一个回溯的步数,这里我们引入KMP算法中的next数组:
    next数组是一个我们存回溯步数的数组,规则为第一个字母存-1,有相同前后缀的存前后缀的大小,其余存0;
    在这里插入图片描述
    c语言实现代码如下:

    void GetNext(str t,int next[]) {
    	int j = 0, k = 1;
    	next[0] = -1; //令第一个为-1
    	while (j < t->length - 1) {	
    		if (k==-1 || t->data[j] == t->data[k]) {	
    			j++;
    			k++;
    			next[j] = k;
           	} else {
    			k = next[k]; 不等时回溯
    		}
    	}
     }
    

    2.KMP算法函数代码:

    代码如下所示:

    int KMPIndex(str s, str t) {
    	int next[MaxSize], i = 0, j = 0;
    	GetNext(t, next);
    	while (i < s->length && j < t->length) {
    		if (j == -1 || s->data[i] == t->data[j]) {
    			i++;
    			j++;  		
    		} else {
    			j=next[j]; //不相等时根据next数组回溯
    		}
    		
        }
        if (j >= t->length) {
        	return(i - t->length);			//若字串在主串中,返回字串在主串中的第一个位置。
    	} else {
    		return(-1);						//若字串不存在,则返回—1;
    	}
    }
    

    总结

    kmp算法适用与处理子串重复出现一些字母的情况,我们在处理这类问题时可以尝试使用kmp算法,初学kmp,有许多不足的地方,还请大家多多包涵。

    展开全文
  • KMP算法代码C语言

    千次阅读 2019-04-09 18:53:39
    KMP ( char s1 [ ] , char s2 [ ] ) { int i = 0 ; int j = 0 ; int len1 = strlen ( s1 ) ; int len2 = strlen ( s2 ) ; while ( i < len1 && j < len2 ) { if ( j == - 1 || s1 [ i ...
  • 数据结构--KMP算法C语言实现

    千次阅读 2018-08-05 21:51:17
    #include #include typedef struct { char *ch; int length; ...int strassign(Str& str,char *ch)... "KMP匹配成功":"KMP匹配失败"; printf("\n%s\n",result1); printf("%s\n",result2); return 0; } 结果:
  • KMP算法 C语言实现

    2012-10-31 00:05:48
    用c实现的KMP算法,没有注释,不过程序逻辑清晰,适合了解算法的人观看
  • #include <stdio.h>...int KMP(char s1[],char s2[],int next[]); int main() { int i= 0; int next[1000]; char s2[] = "abcac"; char s1[] = "ababcabcacbab"; get_next(s2,next); i=KMP(s1,
  • 数据结构 KMP算法 源程序 c语言
  • KMP算法用于判断一个字符串是否包含另一个字符串,如果包含就返回脚标。其实KMP算法本身特别简单,我看了几篇本章都号称简单易懂,结果看得我云里雾里,直到我看到了阮一峰:字符串匹配的KMP算法,才真正看懂。下文的...
  • KMP算法c语言实现

    2009-09-16 16:01:08
    void kmp_matcher(sstring s,sstring s1) { int i = 1,j=1; /* Number of characters mached */ int n = s.length; int m = s1.length; int *x = get_next (s1); while(i) { if(j==0 || s.p[i]==s1.p[j])...
  • 数据结构 - KMP算法C语言实现)

    千次阅读 2019-04-28 18:54:36
    简单模式匹配算法  对某一个串中某子串定位的操作称为串的模式匹配。(注意:求出的是字串在主串中的起始位置)  简单模式匹配算法的思想是:主串与模式串(待定位的串)从第一个位置开始进行比较,如果相等则...
  • KMP算法C语言实现详解

    2021-03-22 16:37:46
    KMP算法C语言实现详解 作者:老九—技术大黍 社交:CSDN 公众号:老九学堂(新手有福利) 特别声明:原创不易,未经授权不得转载或抄袭,如需转载可联系笔者授权 前言 在讲解算法时我先参考了O'Reilly出版的...
  • C语言实现KMP算法

    2020-03-14 21:34:15
    KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配...
  • KMP算法(C语言实现)

    千次阅读 2019-05-03 20:20:36
    我认为 KMP算法中最重要的便是理解next数组,理解为何它就减少了计算量。建议在看视频的过程中手算next数组,然后再写代码。 程序说明:如果主串包含了模式串则打印:匹配成功,反之:匹配失败。...
  • 相对于暴力匹配,kmp匹配在匹配失败后的下一轮匹配中,不一定将模式字符串从头重新开始去匹配,而是在模式字符串中滑动一段才开始匹配,如第四趟匹配 模式字符串滑动多少距离由next数组决定,next数组只与模式串p...
  • 要实现KMP算法首先要解决的就是关于next数组的求解方法。KMP算法的精髓便在于这一点上。可是严蔚敏版的数据结构在这一点上解释的不利于理解。下面是一个来自B站的视频,大家可以作为先修知识理解KMP算法的工作原理...
  • 讲的比较清楚的b站视频 和...文章目录思路写代码前缀表next数组kmp 思路 1.首先制作一个前缀表 对于每一个字符串找到它的最长公共前后缀列表 去掉最后一个 剩下的往后移一位 第一位补-1 做为next数组 补上数组下.
  • kmp算法实现(c语言

    千次阅读 2019-02-20 13:51:05
    kmp算法实现(c语言) 这个kmp算法思路,以及其中的next[]数组的解释可以说是我看过最详细的了,附上链接 #include &amp;lt;stdio.h&amp;gt; #include &amp;lt;string.h&amp;gt; #include &...
  • kmp算法代码实现

    2015-11-17 15:56:11
    数据结构、kmp算法代码实现、KMP(char *P,char *T,int *N,int start)
  • KMP算法--c语言实现

    万次阅读 多人点赞 2015-12-03 11:02:27
    KMP算法 字符串不回溯 搜索词不断移位 搜索词移位时查看是否有重复子串 KMP算法过程 1. 首先,字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符,进行比较。因为B与A不匹配,所以...
  • kmp算法 c语言

    2012-01-05 23:48:00
    kmp算法 c语言 .
  • #include<stdio.h> #include<stdlib.h> #include<string.h> #define MaxSize 50 typedef struct Str{ char ch[MaxSize+1];...//KMP算法 void getNext(Str substr,int next[]){ ...
  • kmp算法c++代码实现(完整版详解)

    千次阅读 多人点赞 2020-02-25 18:23:02
    难理解的还是前后缀表的问题,这个表存的...为什么第一个位置是-1,是因为当他为0的时候在kmp中 当len=0时,(len=prefix[len])之后len=-1,再加1正好是0的下标。 代码 #pragma GCC optimize(3,"Ofast","inline") #...
  • 在网上有很多kmp算法的讲解,大概的框架讲的都还不错,但在next数组的讲解上,我觉得不是很清晰。 在学习KMP算法时,next数组的求解是它的精髓。 在博客中看了许多next数组的求法,推荐一篇kmp算法.我觉得写的非常好...
  • 字符串KMP算法c语言

    2011-09-25 15:56:17
    @字符串KMP算法c.txt@字符串KMP算法c.txt
  • KMP算法C 代码代码实现

    千次阅读 2017-02-07 22:22:59
    其实我是知道next数组的含义的,上网搜了一下很着急,因为全部都在讲怎么求nextval和next数组,却没有一个讲清楚了nextval究竟是个什么东东,大概看了下求法,然后又自己按照next数组实现了一下kmp,顿时领悟了那个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,785
精华内容 1,914
关键字:

kmp算法c语言代码

c语言 订阅