kmp 算法_kmp算法 - CSDN
精华内容
参与话题
  • KMP算法(绝对简单易懂)

    千次阅读 多人点赞 2019-08-29 20:37:01
    KMP算法的作用 比较一个字符串是否为另一个字符串的子串,并可以返回匹配首位置 算法实现过程 1. 首先,字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符,进行比较。因为B与A不...

    KMP算法的作用

    比较一个字符串是否为另一个字符串的子串,并可以返回匹配首位置

     

    算法实现过程

    1.

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


    2.

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

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


    4.

     

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

     


    5.

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


    6.

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


    7.

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


    8.

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


    9.

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


    10.

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


    11.

    因为空格与A不匹配,继续后移一位。


    12.

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


    13.

    逐位比较,直到搜索词的最后一位,发现完全匹配,于是搜索完成。如果还要继续搜索(即找出全部匹配),移动位数 = 7 - 0,再将搜索词向后移动7位,这里就不再重复了。


    14.

    下面介绍《部分匹配表》是如何产生的。
    首先,要了解两个概念:"前缀"和"后缀"。 "前缀"指除了最后一个字符以外,一个字符串的全部头部组合;"后缀"指除了第一个字符以外,一个字符串的全部尾部组合。


    15.

    "部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"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。


    16.

    "部分匹配"的实质是,有时候,字符串头部和尾部会有重复。比如,"ABCDAB"之中有两个"AB",那么它的"部分匹配值"就是2("AB"的长度)。搜索词移动的时候,第一个"AB"向后移动4位(字符串长度-部分匹配值),就可以来到第二个"AB"的位置。

    来自:字符串匹配的kmp算法

     

     

    求解next数组(核心部分)

    1、next数组里面存的是什么值呢?其实就是该位置前的字符串前缀与后缀的共用长度(文中的部分匹配值)-1(说白了就是前后相同的长度-1)

     

     

    实现代码:

    //其实这个你自己静下心模拟一下过程,可以很快理解的
    void kmp_next(char *s)
    {
        int len = strlen(s);
        next[0] = -1;
        int k = -1;
        for(int i = 1; i < len; i ++) {
            while(k > -1 && s[k+1] != s[i]) {
                k = next[k];
            }
            if(s[k+1] == s[i]) {
                k ++;
            }
            next[i] = k;
        }
    }

     

     

    字符串匹配

    相信看懂了前面的描述,你一定理解了匹配过程,接下来就给出匹配过程的代码:(这个其实你完全按照自己理解写,别人的代码仅供参考)

    //理解运用next数组的写法
    void kmp1(char *s1, char *s2)
    {
        int len1 = strlen(s1);
        int len2 = strlen(s2);
        int idx = 0; //s2中匹配的位置
        kmp_next(s2);
        for(int i = 0; i < len1; i ++) {
            if(s1[i] == s2[idx]) {
                idx ++;
            }else {
                if(idx > 0) { //此时不匹配之前有匹配的
                    idx = next[idx-1] + 1;
                    i--; //避免多移一位
                }else idx = 0;
            }
            if(idx == len2) { //完全匹配
                idx = next[idx-1] + 1;
                a[cnt ++] = i-len2+1;
            }
        }
    }
    
    //更高深的写法
    void kmp2(char *s1, char *s2)
    {
        int len1 = strlen(s1);
        int len2 = strlen(s2);
        kmp_next(s2);
        int k = -1;
        for(int i = 0; i < len1; i ++) {
            while(k > -1 && s2[k+1] != s1[i]) { //此时不匹配但是前面有匹配的
                k = next[k];
            }
            if(s2[k+1] == s1[i]) {
                k ++;
            }
            if(k == len2-1) a[cnt ++] = i;
        }
    }

     

    展开全文
  • KMP算法详解

    万次阅读 多人点赞 2019-04-26 20:05:50
    KMP算法是一种字符串模式匹配算法,不同的来源讲解方式也不一样,很容易混乱,在这里以一种特殊的方式来讲解KMP算法,希望大家不再被这个问题所困扰。 一. 一些基础问题 什么是字符串的模式匹配? 给定两个串S=...

    首先感谢大佬博主v_JULY_v(v_JULY_v)在从头到尾彻底理解KMP(2014年8月22日版)一文中给我在写博客组织语言上的启发,以及部分图片的转载。

    KMP算法是一种字符串模式匹配算法,不同的来源讲解方式也不一样,很容易混乱,在这里以一种特殊的方式来讲解KMP算法,希望大家不再被这个问题所困扰。

    一. 一些基础问题

    1. 什么是字符串的模式匹配?
      给定两个串S=“s1s2s3 …sn”和T=“t1t2t3 …tn”,在主串S中寻找子串T的过程叫做模式匹配,T称为模式。
    2. 如何寻找?
      我们先从比较好理解的暴力匹配(朴素模式匹配BF算法)开始,进而引出KMP算法。

    二. 暴力匹配(朴素模式匹配BF)

    规定i是主串S的下标,j是模式T的下标。现在假设现在主串S匹配到 i 位置,模式串T匹配到 j 位置。

    • 如果当前字符匹配成功(即S[i] = T[j]),则i++,j++,继续匹配下一个字符;
    • 如果失配(即S[i] != T[j]),令i = i - (j - 1),j = 0。相当于每次匹配失败时,i 回溯到本次失配起始字符的下一个字符,j 回溯到0。
    int BF(char S[],char T[])
    {
    	int i=0,j=0;
    	while(S[i]!='\0'&&T[j]!='\0')
    	{
    		if(S[i]==T[j])
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			i=i-j+1;
    			j=0;
    		}
    	}
    	if(T[j]=='\0') return (i-j);     //主串中存在该模式返回下标号 
    	else return -1;     //主串中不存在该模式 
    }
    

    我们用一个例子来说明一些这个算法:现在有主串S:ababcabcacbab,模式串T:abcac。我们来看一下是如何匹配的。i从0开始,j也从0开始。

    在第一次匹配中,i从0开始,j从0开始。当i=2,j=2时匹配失败,此时i回溯到1,j回溯到0。
    在这里插入图片描述
    第二次匹配中,i从1开始,j从0开始。当i=1,j=0时匹配失败,此时i回溯到2,j回溯到0。
    在这里插入图片描述
    第三次匹配中,i从2开始,j从0开始。当i=6,j=4时匹配失败,此时i回溯到3,j回溯到0。
    在这里插入图片描述
    第四次匹配中,i从3开始,j从0开始。当i=3,j=0时匹配失败,此时i回溯到4,j回溯到0。
    在这里插入图片描述
    第五次匹配中,i从4开始,j从0开始。当i=4,j=0时匹配失败,此时i回溯到5,j回溯到0。
    在这里插入图片描述
    第六次匹配中,i从5开始,j从0开始。i=10,j=5,T中全部字符比较完,匹配成功,返回本次匹配起始位置下标i - j。(i=9和j=4的时候匹配成功,i和j会再加一次,所以i=10,j=5)
    在这里插入图片描述
    可见,如果i已经匹配了一段字符后出现了失配的情况,i会重新往回回溯,j又从0开始比较。这样浪费的大量的时间。在第三次匹配结束后,我们可以发现:i=3和j=0,i=4和j=0以及i=5和j=0是不必进行的,因为从第三次部分匹配过程中我们可以得出,主串中第3,4,5个字符必然是‘b’,‘c’,‘a’(即与模式串的第1,2,3个字符分别对应相等),而模式的首字符是‘a’,它分别与‘b’,‘c’不等,与‘a’相等。如果将模式向右滑动3个字符继续进行i=6和j=1时的字符比较,很明显会加快进程。这样就引出了我们的KMP算法,不回溯i,加快匹配效率。

    三. KMP算法

    1. 背景
    KMP算法一种改进的模式匹配算法,是D.E.Knuth、V.R.Pratt、J.H.Morris于1977年联合发表,KMP算法又称克努特-莫里斯-普拉特操作。它的改进在于:每当从某个起始位置开始一趟比较后,在匹配过程中出现失配,不回溯i,而是利用已经得到的部分匹配结果,将一种假想的位置定位“指针”在模式上向右滑动尽可能远的一段距离到某个位置后,继续按规则进行下一次的比较。
    2. 算法流程 (这部分读完可能会有很多问题,没关系,我们会针对每一步进行详细的讲解)
    规定i是主串S的下标,j是模式T的下标。现在假设现在主串S匹配到 i 位置,模式串T匹配到 j 位置。

    • 如果j = -1,则i++,j++,继续匹配下一个字符;
    • 如果S[i] = T[j],则i++,j++,继续匹配下一个字符;
    • 如果j != -1,且S[i] != P[j],则 i 不变,j = next[j]。此举意味着失配时,接下来模式串T要相对于主串S向右移动j - next [j] 位。
    int KMP(int start,char S[],char T[])
    {
    	int i=start,j=0;
    	while(S[i]!='\0'&&T[j]!='\0')
    	{
    		if(j==-1||S[i]==T[j])
    		{
    			i++;         //继续对下一个字符比较 
    			j++;         //模式串向右滑动 
    		}
    		else j=next[j];
    	}
    	if(T[j]=='\0') return (i-j);    //匹配成功返回下标 
    	else return -1;                 //匹配失败返回-1 
    }
    

    到这里,我们一点点来引出问题,我们来一一解答(后面的问题引出可能还会引出另一个问题,为方便读者阅读,问题标注成蓝色,对应问题解决的地方标注成红色):

    (1)next是什么???它是怎么来的???

    首先我们来解释一个名词:最长公共前后缀。假设有一个串P=“p0p1p2 …pj-1pj”。如果存在p0p1…pk-1pk = pj-kpj-k+1…pj-1pj,我们就说在P串中有一个最大长度为k+1的公共前后缀。

    (2)如何寻找前后缀???

    • 找前缀时,要找除了最后一个字符的所有子串。
    • 找后缀时,要找除了第一个字符的所有子串。

    问题(2)已解决

    现在有串P=abaabca,各个子串的最大公共前后缀长度如下表所示:
    在这里插入图片描述
    这样,公共前后缀最长长度就会和串P的每个字符产生一种对应关系:
    在这里插入图片描述
    这个表的含义是在当前字符作为最后一个字符时,当前子串所拥有的公共前后缀最长长度。例如当c作为最后一个字符时,当前子串abaabc并没有公共前后缀。
    接下来我们就用这个表来引出next数组,next 数组的值是除当前字符外(注意不包括当前字符)的公共前后缀最长长度,相当于把上表做一个变形,将表中公共前后缀最长长度全部右移一位,第一个值赋为-1。例如c对应next值的意义是,c之前(不包括c)的子串abaab所拥有的公共前后缀最长长度为2,我们称next数组中的值为失效函数值,也就是c的失效函数值为2。(当然这是我们手动推得,我们后续会用编程思想来推得next数组)
    在这里插入图片描述
    我们手动推得了next数组,那就来体验一下KMP算法的流程:现在有主串S:ababcabcacbab,模式串T:abcac。i从0开始,j也从0开始。
    根据上述方法可以知道,T的中每个字符对应的失效函数值为:
    在这里插入图片描述
    第一次匹配中,i从0开始,j从0开始。当i=2,j=2时匹配失败,此时i不动,next[j]=next[2]=0,接下来模式串T要相对于主串S向右移动j - next [j] = 2 位,j回溯到0。
    在这里插入图片描述
    第二次匹配中,i从2开始,j从0开始。当i=6,j=4时匹配失败,此时i不动,next[j]=next[4]=1,接下来模式串T要相对于主串S向右移动j - next [j] = 3位,j回溯到1。
    在这里插入图片描述
    第三次匹配中,i从6开始,j从1开始。当i=10,j=5时匹配成功,返回i - j = 5。
    在这里插入图片描述
    我们根据next数组进行匹配,不失一般性的话,我们做如下总结:
    当主串S与模式串P失配时,j=next[j],P向右移动j - next[j]。也就是当模式串P后缀pj-kpj-k+1…pj-1与主串S的si-ksi-k+1…si-1匹配成功,但是pj和si失配时,因为next[j]=k,相当于在不包含pj的模式串中有最大长度为k的相同前后缀,也就是p0p1…pk-1 = pj-kpj-k+1…pj-1,所以令j = next[j],让模式串右移j - next[j]位,使模式串p0p1…pk-1 与主串si-ksi-k+1…si-1对齐,让pk和si继续匹配。如下图所示:
    在这里插入图片描述
    KMP的next数组告诉我们:当模式串中的某个字符跟主串中的某个字符失配时,模式串下一步应该跳到哪个位置。如模式串中在j 处的字符跟主串在i 处的字符匹配失配时,下一步用next [j] 处的字符继续跟主串i 处的字符匹配,相当于模式串向右移动 j - next[j] 位。

    问题(1)已解决

    好了,至此我们把next原理全部讲完,但是我们不能只停留在手动推导的层面上,我们再从编程下手继续理解next数组,最后再推出KMP算法。

    3. 递推求next数组

    我们很容易的可以知道,next[0] = -1。next[1] = 0也是容易推得的。那么(3)当j>1时,如果我们已知了next[j],那么next[j+1]怎么求得呢???

    假定我们给定了某模式串,且已知next[j] = k,现在求得next[j+1]等于多少。

    我们分两种情况分析:

    1. 当pk=pj时,next[j + 1] = next[j] + 1 = k + 1,代表字符E前的模式串中,有长度k+1 的最大公共前后缀。
      在这里插入图片描述
    2. 当pk ! = pj时,说明p0p1…pk-1pk != pj-kpj-k+1…pj-1pj,这时ABC与ABD不相同,也就是字符E前的模式串中没有长度为k+1的最大公共前后缀,所以next[j + 1] = next[j] + 1不再适用,我们只能寻找更短的最大公共前后缀。
      在这里插入图片描述
      这样看来,如果我们能在p0p1…pk-1pk中不断递归索引k = next[k],找到一个字符pk’,也是D的话,那么最大公共前后缀长度就为k’+1。此时pk’=pj,且p0p1…pk’-1pk’ = pj-k’pj-k’+1…pj-1pj。从而next[j+1] = k’ + 1 = next[k’] + 1。否则前缀没有D,next[j+1] = 0。

    问题(3)已解决

    (4)为什么递归前缀索引k = next[k],就能找到长度更短的相同前缀后缀呢???我们用这张图来分析:
    在这里插入图片描述
    在pk != pj时,k = next[k],用pnext[k]去跟pj继续匹配。为什么不用其他值和pj匹配呢?我们可以看到,在pj之前,有一段长度为k的已匹配串;在pk之前有一段蓝色的已匹配串,说明pk字符前有一段长度为next[k]的最大公共前后缀(蓝色的那段)。如果pk != pj,说明p0p1…pk-1pk != pj-kpj-k+1…pj-1pj,那么我们只能找更短的最大公共前后缀,此时因为pk和pnext[k]前面的蓝色串已完全匹配,如果pnext[k]能和pj匹配 ,那么我们便找到了我们需要的串。如果还是不匹配,下一步pnext[next[k]…]去跟pj继续匹配,直到找到长度更短公共前后缀。
    问题(4)已解决
    综上,我们可以写出求next数组的递推代码:

    void GetNext(char T[])
    {
    	int j=0,k=-1;
    	next[j]=k;
    	while(T[j]!='\0')
    	{
    		if(k==-1||T[j]==T[k])
    		{
    			j++;
    			k++;
    			next[j]=k;
    		}
    		else k=next[k];
    	}
    }
    

    其实,我们在分析的过程中可以发现,k=next[next[k]…]这一步其实非常的类似于递归。因此我们也给出递归的代码供读者参考。

    int GetNext(int j,char T[])
    {
    	if(j==0)return -1;
    	if(j>0)
    	{
    		int k=GetNext(j-1,T);
    		while(k>=0)
    		{
    			if(T[j-1]==T[k])return k+1;
    			else k=GetNext(k,T);
    		}
    		return 0;
    	}
    	return 0;
    }
    
    展开全文
  • KMP算法--c语言实现

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

    KMP算法

    • 字符串不回溯
    • 搜索词不断移位
    • 搜索词移位时查看是否有重复子串

    KMP算法过程

     1.这里写图片描述

      首先,字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符,进行比较。因为B与A不匹配,所以搜索词后移一位。
      2.
    这里写图片描述
      因为B与A不匹配,搜索词再往后移。
      3.
    这里写图片描述
      就这样,直到字符串有一个字符(不断向前移动),与搜索词的第一个字符相同为止。
      4.
    这里写图片描述
      接着比较字符串和搜索词的下一个字符,还是相同。
      5.
    这里写图片描述
      直到字符串有一个字符,与搜索词对应的字符不相同为止。
      6.这里写图片描述

      这时,按照暴力解法(穷举法),将搜索词整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把”搜索位置”移到已经比较过的位置,重比一遍。
      7.
    这里写图片描述
      一个基本事实是,当空格与D不匹配时,你其实知道前面六个字符是”ABCDAB”。KMP算法的思想是,设法利用这个已知信息,不要把”搜索位置”移回已经比较过的位置(不回溯),继续把它向后移,这样就提高了效率。
      8.
    这里写图片描述
      怎么做到这一点呢?可以针对搜索词,算出一张《部分匹配表》(Partial Match Table)。这张表是如何产生的,后面再介绍。
      9.
    这里写图片描述
      已知空格与D不匹配时,前面六个字符”ABCDAB”是匹配的。查表可知,最后一个匹配字符B对应的”部分匹配值”为2,因此按照下面的公式算出向后移动的位数:
      移动位数 = 已匹配的字符数 - 对应的部分匹配值
      因为 6 - 2 等于4,所以将搜索词向后移动4位。
      10.
    这里写图片描述
      因为空格与C不匹配,搜索词还要继续往后移。这时,已匹配的字符数为2(”AB”),对应的”部分匹配值”为0。所以,移动位数 = 2 - 0,结果为 2,于是将搜索词向后移2位。
      11.
    这里写图片描述
      因为空格与A不匹配,继续后移一位。
      12.
    这里写图片描述
      逐位比较,直到发现C与D不匹配。于是,移动位数 = 6 - 2,继续将搜索词向后移动4位。
      13.
    这里写图片描述
      逐位比较,直到搜索词的最后一位,发现完全匹配,于是搜索完成。如果还要继续搜索(即找出全部匹配),移动位数 = 7 - 0,再将搜索词向后移动7位,这里就不再重复了。
      14.
    这里写图片描述
      下面介绍《部分匹配表》是如何产生的。
      首先,要了解两个概念:”前缀”和”后缀”。 “前缀”指除了最后一个字符以外,一个字符串的全部头部组合;”后缀”指除了第一个字符以外,一个字符串的全部尾部组合。
      15.
    这里写图片描述
      “部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”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。
      “部分匹配”就是(判断子串是否有重复)字符串头部和尾部会有重复。比如,”ABCDAB”之中有两个”AB”,那么它的”部分匹配值”就是2(”AB”的长度)。搜索词移动的时候,第一个”AB”向后移动4位(字符串长度-部分匹配值),就可以来到第二个”AB”的位置。

    简易实现代码(不喜勿喷):

    #include "stdio.h"
    #include "stdlib.h"
    #include "string.h"
    
    #define ERROR 0;
    #define TRUE 1;
    //初始化数据
    int InitData(char **source,char **target,int **value){
    
        char ch;
        int i = 0;
    
        (*source) = (char *)malloc(sizeof(char) *100);
        (*target) = (char *)malloc(sizeof(char) *100);
        (*value) = (int *)malloc(sizeof(int) *100);
    
    
        if(!(*source) || !(*target) || !(*value))return ERROR;
    
        printf("请输入要输入源字符串,以#结束:\n");
    
        while((ch = getchar())!='#'){
    
            (*source)[i++] = ch;
            (*source)[i] = '\0';
        }
        getchar();  //抵消缓冲
    
        i = 0;  //重置
        printf("请输入要匹配的字符串,以#结束:\n");
    
        while((ch = getchar())!='#'){
            (*target)[i++] = ch;
            (*target)[i] = '\0';
        }
    
        //初始化value数组
        for(i = 0; i < 100;i++){
            (*value)[i] = 0;
        }
        return TRUE;
    }
    
    
    //得出target中的匹配值
    int GetValue(char * target, int *value){  
    
        char *head,*tail;
        int temp;
        //ABCDABD
        //ABCDAB
        int i = 1,j = 0;
        head = (char *)malloc(sizeof(char) *100);
        tail = (char *)malloc(sizeof(char) *100);
        if(!head || !tail)return ERROR;
    
        for(i = 1;i<strlen(target);i++){  //从头到尾
    
            j = 0;
            while(target[j]!='\0'){  //复制到临时数组
                head[j] = target[j];
                tail[j] = target[j];
                j++;
                head[j]='\0';
                tail[j] = '\0';
            }
    
            head[i] = '\0';
            tail[i+1] = '\0';
    
            for(j = 0;j<i;j++){
                if(strcmp(head,tail+1+j)==0){  //比较
                    value[i] = strlen(head);
                    break;
                }
                temp = strlen(head) - 1;
                head[temp] = '\0';
            }
        }
    }
    
    //KMP处理过程
    int KMP(char *source,char *target,int *value){
    
        int i = 0,j = 0;
    
        while(i < strlen(source)){  //不回溯,source走到尾
    
            if(source[i] == target[j] && j<strlen(target)){
                i++;
                j++;
            }else if(j>=strlen(target)){
                printf("找到...");
                return TRUE;
    
            }else if(source[i]!=target[j]){
                if(j==0){
                    j=0;
                    i++;
                }else{
                    j =  value[j-1];
                }
            }
        }
        if(i >=strlen(source) && j>=strlen(target))printf("找到...");
        else printf("未找到...");
        return ERROR;
    }
    int main(){
        char *source,*target; //source源字符串,target要匹配的字符串
        int *value;  //存放匹配值
        int i = 0;
    
        InitData(&source,&target,&value);  //初始化字符串
        GetValue(target,value);
        KMP(source,target,value);
    }
    展开全文
  • 通俗易懂的KMP算法详解(严蔚敏版C语言)

    千次阅读 多人点赞 2019-03-16 09:33:44
    最近,需要复习KMP算法的next数组,然后回头看半年多后的我回头看半年多前自己综合别人内容写的介绍。 没错,自己也看不懂。然后,自己再根据自己的理解写了一下理解透彻的笔记,方便理解记忆,当然,以前的代码解释...

     

        最近,需要复习KMP算法的next数组,然后回头看半年多后的我回头看半年多前自己综合别人内容写的介绍。     没错,自己也看不懂。然后,自己再根据自己的理解写了一下理解透彻的笔记,方便理解记忆,当然,以前的代码解释部分可以参考,笔记算法思维和算法的实现有一定的出入。望君谅解。(2018.9.30)

          

                                                                                

                                                                               这是一条时间分割线

    _____________________________________________________________________________________________________

       

        从刚接触算法,感觉是跟不上的一片片片段,再往后自己看书理解,片段更是碎成一点点乱码。在下愚钝,在查询多种博客,结合书上(严蔚敏的数据结构)解释和代码,询问教师,后终于开窍。在此处引用了阮先生的部分思想,来通俗的讲解一下KMP算法。

       BMP算法与BF算法的根本区别

         解读BMP之前,我们先来理解一下BMP算法存在的理由。对于模式匹配,目前所学的最简单的是BF算法,即偏向于“暴力”匹配的方法。另外一种就是较为复杂BMP算法了。而俩者的区别在于:BF算法是时间复杂度相对高的,KMP则可以理解为用空间换时间。

         BF算法:        逐个匹配主串字符,然后模式串j值回溯到1重新匹配。

         KMP算法:       KMP只需要将j值模式串中j的位置回溯到next[j]位,而免除了前面不需要的匹配,以此来换取时间。

    图片:

     相比一个一个比较,同学们肯定会更加想询问为什么不直接从模式串第一个字符和主串相同字符的位置比较即:       

    图片:

         而BMP则在此基础上更加的简便了。

          接下来,我们来用有逻辑的语言来了解KMP算法。而后,再解释如何用代码实现该算法。

         首先,我们从代码的实现效果来看,主串与模式串每次历往KMP算法,模式串中移动至K位与失配的(主串)的i位对其,而不需要像BF算法一样,一次次回溯从头开始。

         那么,问题来了。K为何物?

         在此之前,我们来介绍一下最长前缀和最长后缀,和部分匹配。

         移动位数 =  已匹配值   -    部分匹配值     (其实就是直接从最长前缀直接跳到与他相等的最长后缀那里开始往后匹配)

     

    上面都可以不用看

        效果大概是这样子:

    以模式串ABCDABD,文本串BBCABCDABABCDABCDABDE为例子展示最大公共元素长度(最长前缀和他相等的最长后缀)。

     

         再来一遍:移动位数 =  已匹配值   -    最大公共元素长度

    关键是计算next数组的值。

    计算next数组的值,伪代码如下:

    void get_next(SString T, int[] next){
         /*求模式串T的next函数值并存入数组next*/
           i=1; next[1]=0; j=0;
           while(i<T.length)
            {
              if(j==0||T.ch[i]==T.ch[j])
                {
                    ++i;++j;             //相符合,前缀位数和后缀位数后退
                    next[i]=j;
                }else{
                     j=next[j];    //前n位前缀不符合后n位后缀,使i待定,往前一位退,探测n-1位前缀和后缀是否符合
                     /**如果一直不符合,那么将一直退到0,进入if语句,i++下一位探测**/
                }
            
           }
    }

    解释next数组代码运算过程

           next数组next[1]、next[2]固定为0,1,除next后还有next修正值,这里不讲。

           以abaabc为例子(前面俩步自己按代码思维过一遍): 第一个j=1(a),i=3(a) 

     

         ps:总之就是,先从第一个跟第二个比较,若成功就右滑比较,假设比较到三位连续相等:最大公共元素长度为3,第四位不等。  因为新增一个比较位,后缀的开头第一个改变需要重新比较(abc——>后缀:cba,;    abcd——>后缀:dcba),j回退一位,比较最大公共元素长度为3是否相等,不等继续后退减一(i一直为改变)。直到j=0,进入if语句,i++,下一个比较。计算next值的过程实质是计算模式串各个子串的最大公共元素长度。详细见最大公共元素长度效果图。然后方便模式串匹配文本串的时候,模式串直接从最长前缀直接跳到与他相等的最长后缀那里开始往后匹配。

     

    下面是kmp的伪代码:

      

    int index_KMP(SString S ,SString T, int[] next){//S为文本串,T为模式串
       while(i<=S.length && j<=T.length){
        
        if(j==0 || S.char[i]==T.char[j]){
                j++;i++;            //后一位是否连续性匹配
       }else j=next[j];            //从模式串的第j位开始和后面匹配,就是直接从最长前缀直接跳到与他相等的最长后缀那里
       
       if(j>T.length)
       {
           return i-T.length;   //匹配成功
       }else{
        return 0;             //匹配失败
       }
    
    
    }

     

     

     

    展开全文
  • 数据结构之KMP算法(转)

    千次阅读 2018-07-02 20:48:58
    申明:此篇博文为转载博文,原博文地址:https://www.cnblogs.com/yjiyjige/p/3263858.html什么是...KMP算法要解决的问题就是在字符串(也叫主串)中的模式(pattern)定位问题。说简单点就是我们平时常说的关键字...
  • KMP算法

    万次阅读 多人点赞 2020-07-27 17:28:59
    先来一波代码 : #include <iostream> #include <cstdio> #include <cstring> using namespace std ; const int MAX = 1005 ; typedef long long LL ;...void getNext(char *...
  • KMP算法—终于全部弄懂了

    万次阅读 多人点赞 2019-03-22 21:00:45
    详细讲解KMP算法,并对难点 k=next[k] 这条语句重点描述
  • KMP算法——很详细的讲解

    万次阅读 多人点赞 2018-09-09 10:56:56
    KMP算法(研究总结,字符串) KMP算法(研究总结,字符串) 前段时间学习KMP算法,感觉有些复杂,不过好歹是弄懂啦,简单地记录一下,方便以后自己回忆。 引入 首先我们来看一个例子,现在有两个字符串A和B,...
  • KMP算法最浅显理解——一看就明白

    万次阅读 多人点赞 2018-04-03 16:21:46
    KMP算法看懂了觉得特别简单,思路很简单,看不懂之前,查各种资料,看的稀里糊涂,即使网上最简单的解释,依然看的稀里糊涂。 我花了半天时间,争取用最短的篇幅大致搞明白这玩意到底是啥。 这里不扯概念,只讲...
  • 上:http://v.youku.com/v_show/id_XODYxNjExODQ=.html 第 34分钟开始  下:http://www.56.com/u28/v_NjAwMzA0ODA.html  严蔚敏
  • KMP算法的简单总结以及java代码实现

    万次阅读 2016-04-27 11:00:37
    做了好几天KMP的题,今天终于写好了,可以总结一下这么多天学到的东西了,结合了众多版本之后觉得还是July写的最好,KMP是一个解决模式串在文本串是否出现过,以及若是出现时,最早出现的位置的经典算法。...
  • KMP算法代码实现

    千次阅读 2018-04-26 15:00:27
    KMP算法的核心思想是避免匹配失败时重新从短串的第一个字符开始匹配,从而提高匹配效率。#include &lt;iostream&gt; #include&lt;cstdio&gt; #include&lt;cstdlib&gt; #include&lt;...
  • 超详细理解:kmp算法next数组求解过程和回溯的含义

    万次阅读 多人点赞 2018-06-11 09:41:44
    前言KMP算法是用来求一个较长字符串是否包含另一个较短字符串的算法。具体算法下一篇写吧,这篇主要解释next数组的求解。
  • KMP算法--Next数组详解与优化

    万次阅读 2018-11-15 17:54:28
    1.1 KMP算法的应用:KMP算法用来解决模式串匹配问题。 1.2 为什么要用KMP算法:普通的蛮力算法时间复杂度为O(n*m),而KMP为O(n+m)。 2.KMP算法思想 2.1 KMP算法的思想:(称T为目标串,P为待查找字串) 目标...
  • Algorithm:C++语言实现之字符串相关算法(字符串的循环左移、字符串的全排列、带有同个字符的全排列、串匹配问题的BF算法和KMP算法) 目录 一、字符串的算法 1、字符串的循环左移 2、字符串的全排列 3、带有...
  • BF,KMP,BM三种字符串匹配算法性能比较
  • KMP时间复杂度分析

    千次阅读 2018-03-16 11:52:57
    比较过程分析比较次数 比较次数: 红色 + 蓝色 蓝色部分是相比暴力求解,节省下的比较次数 周期从比较次数可以看出,呈现 1 1 1 1 5 这样的周期 一个周期内的比较次数:8 周期长度:5 周期个数:n/5 ...
  • KMP算法Next数组计算

    万次阅读 多人点赞 2018-06-28 22:45:38
    KMP算法是在最近这两年的软件设计师考试中才出现的。2次都是让求Next函数的序列(其实是)。先看看题吧。 (2011年下半年上午题) (2012年上半年上午题) 其实做这个题很简单,我先说说这个题里的各种概念。...
  • 最近在学kmp算法,但是看了网上好多的讲解,都觉得好乱,有谁能给一个比较容易理解的版本么? 谢谢啦!
  • KMP算法的时间复杂度

    千次阅读 2017-07-14 16:45:22
    在学习程杰老师的大作《大话数据结构》时,遇到KMP算法始终没有看明白, 在网上搜索后找到并阅读了阮一峰老师对KMP算法的解释后,茅塞顿开,便按照文章思想编写了算法代码, 算法代码链接:...
1 2 3 4 5 ... 20
收藏数 36,901
精华内容 14,760
关键字:

kmp 算法