精华内容
下载资源
问答
  • 大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的...

    大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的结果整理出来,与大家一起探讨。

    本文的逻辑顺序为
    1、最基本的朴素算法
    2、优化的KMP算法
    3、应算法需要定义的next值
    4、手动写出较短串的next值的方法
    5、最难理解的、足足有5行的代码的求next值的算法
    所有铺垫为了最后的第5点,我觉得以这个逻辑下来,由果索因还是相对好理解的,下面写的很通俗,略显不专业…

    一、问题描述

    给定一个主串S及一个模式串P,判断模式串是否为主串的子串;若是,返回匹配的第一个元素的位置(序号从1开始),否则返回0;如S=“abcd”,P=“bcd”,则返回2;S=“abcd”,P=“acb”,返回0。

    二、朴素算法

    最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例,一张动图模拟朴素算法:

    在这里插入图片描述
    这个算法简单,不多说,附上代码

    #include<stdio.h>
    int Index_1(char s[],int sLen,char p[],int pLen){//s为主串,sLen为主串元素个数,p为模式串,pLen为模式串的个数
        if(sLen<pLen)return 0;
        int i = 1,j = 1;
        while(i<=sLen && j<=pLen){
            if(s[i]==p[j]){i++;j++;}
            else{
                i = i-j+2;
                j = 1;
            }
        }
        if(j>pLen) return i-pLen;
        return 0;
    }
    void main(){
        char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
        char p[]={' ','a','b','a','a','b','c','a','c'};
        int sLen = sizeof(s)/sizeof(char)-1;
        int pLen = sizeof(p)/sizeof(char)-1;
        printf("%d",Index_1(s,sLen,p,pLen));
    }
    

    三、改进的算法——KMP算法

    朴素算法理解简单,但两个串都有依次遍历,时间复杂度为O(n*m),效率不高。由此有了KMP算法。
    一般的,在一次匹配中,我们是不知道主串的内容的,而模式串是我们自己定义的。
    朴素算法中,P的第j位失配,默认的把P串后移一位。
    但在前一轮的比较中,我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着,在一轮的尝试匹配中,我们get到了主串的部分内容,我们能否利用这些内容,让P多移几位(我认为这就是KMP算法最根本的东西),减少遍历的趟数呢?答案是肯定的。再看下面改进后的动图:
    在这里插入图片描述

    这个模拟过程即KMP算法,若没有看明白,继续往下看相应的解释,理解需要把P多移几位,然后回头再看一遍这个图就很明了了。

    相比朴素算法:
    朴素算法: 每次失配,S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1;T(n)=O(n*m)
    KMP算法: 每次失配,S串的索引i不动,P串的索引j定位到某个数。T(n)=O(n+m),时间效率明显提高

    而这“定位到某个数”,这个数就是接下来引入的next值。(实际上也就是P往后移多少位,换一种说法罢了:从上图中也可以看出,失配时固定i不变,令S[i]与P[某个数]对齐,实际上是P右移几位的另一种表达,只有为什么这么表达,当然是因为程序好写。)

    开——始——划——重——点!(图对逻辑关系比较好理解,但i和j的关系对后面求next的算法好理解!)

    • 比如,Pj处失配,绿色的是Pj,则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
      在这里插入图片描述

    • 假设P1…Pj-1中,P1…Pk-1与Pj-k+1…Pj-1是一一相等的,为了下面说的清楚,我们把这种关系叫做“首尾重合”
      在这里插入图片描述

    • 那么可以推出,P1…Pk-1与Si…Si+j-2
      在这里插入图片描述

    • 显然,接下来要做的就是把模式串右移了,移到哪里就不用多说了:
      在这里插入图片描述

    • 为了表示下一轮比较j定位的地方,我们将其定义为next[j],next[j]就是第j个元素前j-1个元素首尾重合部分个数加一,当然,为了能遍历完整,首尾重合部分的元素个数应取到最多,即next[j]应取尽量大的值,原因挺好理解的,可以想个例子模拟一下,会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即,对于字符串P,next[8]=4。如此,再看一下上面的动图是不是清楚了不少。

    • 最后,如果我们知道了一个字符串的next值,那么KMP算法也就很好懂了。相比朴素算法,当发生失配时,i不变,j=next[j]就好啦!接下来就是怎么确定next值了。

    四、手动写出一个串的next值

    我们规定任何一个串,next[1]=0。(不用next[0],与串的所有对应),仍是一张动图搞定问题:
    在这里插入图片描述
    这个扫一眼就能依次写出,会了这个方法,应付个期末考试没问题了。

    通过把next值“看”出来,我们再来分析next值,这就很容易得到超级有名的公式了,这个式子对后面的算法理解很重要!所以先要看懂这个式子,如果上面的内容通下来了,这个应该很容易看懂了:
    在这里插入图片描述

    五、求next的算法

    终于到了最后了~短的串的next值我们可以“看”出来,但长的串就需要借助程序了,具体算法刚接触的时候确实不容易理解,但给我的体验,把上面的内容写完,现在感觉简简单单了…先附上程序再做解释,(终于到了传说中的整整5行代码让我整理了一下午)。

    int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
        next[1] = 0;
        int i = 1,j = 0;
        while(i<=cLen){
            if(j==0||ch[i]==ch[j]) next[++i] = ++j;
            else j = next[j];
        }
    }
    
    • 还是先由一般再推优化:
      直接求next[j+1](至于为什么是j+1,是为了和下面的对应)
      根据之前的分析,next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件,把它的值一步步“检验”出来。一是“个数最多”的,因此要从可能的最大值开始验;二是“首尾重合”,因此要一一对应验是否相等。
      不难理解,next[j+1]的最大值为j,所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序:
      if(P1…Pj-1 == P2…Pj) => next[j+1]=j
      else if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
      else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2



      else if(P1P2 == Pj-1Pj) => next[j+1]=3
      else if(P1 == Pj-1) => next[j+1]=2
      else if(P1 != Pj-1) => next[j+1]=1

      每次前去尾1个,后掐头1个,直至得到next[j+1]

    • 再进一步想,next值是一个“工具”,我们单独的求next[j+1]是完全没有意义的,就是说要求next就要把所有j的next求出来。所有一般的,我们都是已知前j个元素的next值,求next[j+1],以此递推下去,求完整的next数组
      但是,上面的思考过程还是最根本的。所以问题变为两个:知道前j个元素的next的情况下,
      ①next[j+1]的可能的最大值是多少(即从哪开始验证)
      ②某一步验证失败后,需要“前去尾几个,后掐头几个?”(即本次验证失败后,再验证哪个值)
      看一下的分析:

    1、next[j+1]的最大值为next[j]+1。
    因为:
    假设next[j]=k1,则可以说明P1…Pk1-1=Pj-k1+1…Pj-1,且这是前j个元素最大的首尾重合序列。
    如果Pk1=Pj,那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj,那么k+1这也是前j+1个元素的最大首尾重合序列,也即next[j+1]的值为k1+1
    2、如果Pk1≠Pj,那么next[j+1]可能的次大值为next[next[j]]+1,以此类推即可高效求出next[j+1]
    这里不好解释,直接看下面的流程分析及图解

    开——始——划——重——点!
    从头走一遍流程
    ①求next[j+1],设值为m
    已知next[j]=k1,则有P1…Pk1-1 = Pj-k1+1…Pj-1
    如果Pk1=Pj,则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj,则next[j+1]=k1+1,否则
    已知next[k1]=k2,则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
    ⑤第二第三步联合得到:
    P1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
    ⑥这时候,再判断如果Pk2=Pj,则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj,则next[j+1]=k2+1;否则再取next[k2]=k3…以此类推

    上面几步,耐心看下来,结合那个式子很容易看懂。最后,再加一个图的模拟帮助理解:
    1、要求next[k+1] 其中k+1=17
    在这里插入图片描述
    2、已知next[16]=8,则元素有以下关系:
    在这里插入图片描述
    3、如果P8=P16,则明显next[17]=8+1=9
    4、如果不相等,又若next[8]=4,则有以下关系

    在这里插入图片描述
    又加上2的条件知
    在这里插入图片描述
    主要是为了证明:
    在这里插入图片描述
    5、现在在判断,如果P16=P4则next[17]=4+1=5,否则,在继续递推
    6、若next[4]=2,则有以下关系
    在这里插入图片描述
    7、若P16=P2,则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0;遇到0时还没出结果,则递推结束,此时next[17]=1。最后,再返回看那5行算法,应该很容易明白了!

    展开全文
  • 在关于字符定位的算法中,朴素模式匹配算法极其低效。在很多年前我们的科学家们,觉得像有多个重复字符的字符, 却需要挨个遍历的算法是非常糟糕的事情。 于是有三位前辈, D.E....以下为利用Java语言实现的KMP算法

    在关于字符串定位的算法中,朴素模式匹配算法极其低效。在很多年前我们的科学家们,觉得像有多个重复字符的字符串, 却需要挨个遍历的算法是非常糟糕的事情。 于是有三位前辈, D.E.Knutb、****J.H.MorrisV.R.Pratt(其中Knuth 和Pratt共同研究, Morris独立研究)发表了一个模式匹配算法,可以大大避免重复遍历的情况, 我们把它称之为克努特一莫里斯—普拉特算法, 简称KMP算 法。
    朴素模式匹配算法与KMP模式匹配算法的原理不在此说明。以下为利用Java语言实现的KMP算法的代码。

    import java.util.*;
    
    public class kmp{
    	//计算要匹配的串T的next数组
    	public void getNext(String T,int[] next) {
    		int i = 0;
    		int j = -1;
    		next[0] = -1;
    		while(i < T.length()-1) {
    			if (j == -1||T.charAt(i) == T.charAt(j)) {
    				++i;
    				++j;
    				next[i] = j;
    			}else
    				j = next[j];
    		}
    	}
    	
    	public int Kmp(String S,String T) {
    		int i = 0;
    		int j = 0;
    		int sl = S.length();
    		int tl = T.length();
    		int[] next = new int[tl];
    		getNext(T,next);
    		while(i < sl && j < tl) {
    			if(S.charAt(i) == T.charAt(j)) {
    				i++;
    				j++;
    			}else {
    				if (next[j] == -1) {
    					i++;
    					j = 0;
    				}else {
    					j = next[j];
    				}
    			}
    			if (j >= tl) {
    				return i-tl+1;
    			}
    		}
    		return -1;	
    	}
    	public static void main(String[] args) {
    		kmp k = new kmp();
    		Scanner in = new Scanner(System.in);
    		System.out.print("Please input a main String!");
    		String S = in.nextLine();
    		System.out.println();
    		System.out.print("Please input a pattern!");
    		String T = in.nextLine();
    		System.out.println("position: "+k.Kmp(S, T));
    		in.close();
    	}
    }
    

    运行结果如下:

    在这里插入图片描述

    展开全文
  • 数据结构与算法 -- 字符匹配 KMP算法字符匹配KMP算法 原理next 数组推导KMP 算法代码实现KMP 算法优化KMP 算法优化实现 字符匹配 题目: 给一个仅包含小写字母字符 S = abcacabdc,模式 T = abd...

    字符串匹配

    题目:

    给一个仅包含小写字母的字符串主串 S = abcacabdc,模式串 T = abd,请查找出模式串在主中第一次出现的位置;

    提示:主串和模式串均为小写字母
    

    KMP算法 原理

    对于这道算法题的解法,之前结束了BF算法RK算法BF算法是最好理解的,依次对比模式串主串的各个字符,直到完全匹配,而RK算法解题,是将主串依次拆分为n模式串长度的子串,并对其通过哈希算法换算成哈希值,进行比较。

    而在利用BF算法解题时,会出现下面的情况:

    假设主串S = abcababca,模式串T = abcabx,则会出现下面的比较


    当比较到最后一个字符X时,不相等,则平移。
    当进行到下面的比较时

    发现前面两个对ab的比较是多余。

    因此,可以定义一个数组next,数组的长度为模式串的长度,数组中来存储在进行匹配时,模式串标记j回溯的位置。如下图,直接从j = 3的位置开始比较。

    而这就是KMP算法的原理。KMP算法主要是对模式串进行分析处理,依次找出模式串中相同的字符,当有相同字符的时候,j的回溯位置。而next数组的推导是KMP算法的关键。

    next 数组的推导

    • 第一种情况,模式串的字符都不相同时

      假如:模式串T = abcdex

      当 j = 1 时,next[1] = 0(第一个字符匹配失败,回溯到开始的位置)
      当 j = 2 时,匹配字符'b',此时 1 到 j - 1 的范围内只有'a',没有相同的字符,匹配失败时,需要从头
                  开始即重新匹配'a',next[2] = 1
      当 j = 3 时,匹配字符'c',此时 1 到 j - 1 的范围内只有'ab',没有相同的字符,匹配失败时,需要从头
                  开始即重新匹配'a',next[3] = 1
      依次类推...
      next[4] = 1  next[5] = 1 next[6] = 1
      

    • 第二种情况,模式串有相等的字符时

      假如:模式串T = abcabx

      当 j = 1 时,next[1] = 0(第一个字符匹配失败,回溯到开始的位置)
      当 j = 2 时,此时 1 到 j - 1 的范围内只有'a',没有相同的字符,匹配失败时,需要从头
                  开始即重新匹配'a',next[2] = 1
      当 j = 3 时,此时 1 到 j - 1 的范围内只有'ab',没有相同的字符,匹配失败时,需要从头
                  开始即重新匹配'a',next[3] = 1
      当 j = 4 时,此时 1 到 j - 1 的范围内只有'abc',没有相同的字符,匹配失败时,需要从头
                  开始即重新匹配'a',next[4] = 1
      当 j = 5 时,此时 1 到 j - 1 的范围内只有'abca',显然前缀字符'a'与后缀字符'a'相等,匹配
                  失败时,可以从字符'b'开始,(P1 - Pk-1 = Pj-k+1 ... Pj-1,得到P1 = P4),
                  因此推出 k = 2,因此 next[5] = 2
      当 j = 6 时,此时 1 到 j - 1 的范围内只有'abcab',显然前缀字符'ab'与后缀字符'ab'相等,匹配
                  失败时,可以从字符'c'开始,(P1 - Pk-1 = Pj-k+1 ... Pj-1,得到[P1,P2] = [P4, P5]),
                  因此推出 k = 3,因此 next[5] = 3
      

    经验: 如果前后缀一个字符相等,K = 2,两个字符相等,K = 3,n个字符相等,K = n + 1

    • next 数组 回溯理解

      假设主串 S = abcababca,模式串T = abcabxiT的开始下标,从i = 0开始,jT结束的下标,从j = 1开始。

      • i = 0, j = 1

         1.默认 next[1] = 0
         2.i = 0,j = 1,j < T.length,j 从 1-length 开始遍历字符串,
         3.当 i=0 时,表示模式串 T 中【i,j】范围内没有找到相同的字符,所以 i 要回溯到 1 的位置,
         表示 next[j] = i,即next[1] = 0;
         4.或者 T[i] = T[j],表示找到相等的字符的位置,next[j] = i
         5.不满足以上两个条件,将 i 回溯到 next[i] 的位置。
         
         判断T[i] != T[j],但是 i = 0,表示【0,1】,这个范围【a】,只能从 1 的位置开始,
         扩大查找相同字符的范围
         所以 i++,j++,i = 1, j = 2,更新 next[j] = i,即:next[2] = 1
        
      • i = 1, j = 2

         比较【1,2】范围内是否有相同的字符,
         
         判断T[1] != T[2](a != b),所以 i 要回溯,i = next[i] = next[1] = 0
         此时,i = 0, j = 2
        
      • i = 0, j = 2

         比较【0,2】范围内是否有相同的字符,
         i = 0,又要重头开始比较,扩大查找相同字符的范围,i++,j++,
         i = 1,j = 3
         更新 next[j] = i,即:next[3] = 1
        
      • i = 1, j = 3

         比较【1,3】范围内是否有相同的字符,
         
         判断T[1] != T[3](a != c),所以 i 要回溯,i = next[i] = next[1] = 0
         此时,i = 0, j = 3
        
      • i = 0, j = 3

          比较【0,3】范围内是否有相同的字符,没有相同的字符
          i = 0,又要重头开始比较,扩大查找相同字符的范围,i++,j++,
          i = 1,j = 4
          更新 next[j] = i,即:next[4] = 1
        
      • i = 1,j = 4

          比较【1,4】范围内是否有相同的字符,
          判断T[1] = T[4](a = a),扩大查找范围,是否有更长的相同字符
          i++,j++, i = 2, j = 5
          更新 next[j] = i,即:next[5] = 2
        
      • i = 2, j = 5

          比较【2,5】范围内是否有相同的字符,
          判断T[2] = T[5](b = b),扩大查找范围,是否有更长的相同字符
          i++,j++, i = 3, j = 6
          更新 next[j] = i,即:next[6] = 3
          
          j = 6时,模式串 T 已经处理查找完毕
        

    总结:

     在求解 next 数组的4中情况
     1. 默认 next[1] = 0
     2. 当 i= 0,表示当前的比较应该从头开始,则i++,j++,next[j] = i
     3. 当 T[i] = T[j],表示两个字符相等,则i++,j++,next[j] = i
     4. 当 T[i] != T[j],表示两个字符不相等,则将 i 回退到合理的位置,则 i = next[i]
    
    • next 数组求解 代码
    // T 为模式串,T[0]位置存储T的长度
    void get_next(String T,int *next){
        int i,j;
        j = 1;
        i = 0;
        next[1] = 0;
        //abcdex
        //遍历T模式串, 此时T[0]为模式串T的长度;
        //printf("length = %d\n",T[0]);
        while (j < T[0]) {
            //printf("i = %d j = %d\n",i,j);
            if(i ==0 || T[i] == T[j]){
                //T[i] 表示后缀的单个字符;
                //T[j] 表示前缀的单个字符;
                ++i;
                ++j;
                next[j] = i;
                //printf("next[%d]=%d\n",j,next[j]);
            }else
            {
                //如果字符不相同,则i值回溯;
                i = next[i];
            }
        }
    }
    
    

    KMP 算法代码实现

    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define MAXSIZE 100 /* 存储空间初始分配量 */
    
    typedef int Status;        /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
    typedef int ElemType;    /* ElemType类型根据实际情况而定,这里假设为int */
    typedef char String[MAXSIZE+1]; /*  0号单元存放串的长度 */
    
    //----字符串相关操作---
    /* 生成一个其值等于chars的串T */
    Status StrAssign(String T,char *chars)
    {
        int i;
        if(strlen(chars)>MAXSIZE)
            return ERROR;
        else
        {
            T[0]=strlen(chars);
            for(i=1;i<=T[0];i++)
                T[i]=*(chars+i-1);
            return OK;
        }
    }
    
    Status ClearString(String S)
    {
        S[0]=0;/*  令串长为零 */
        return OK;
    }
    
    /*  输出字符串T。 */
    void StrPrint(String T)
    {
        int i;
        for(i=1;i<=T[0];i++)
            printf("%c",T[i]);
        printf("\n");
    }
    
    /* 返回串的元素个数 */
    int StrLength(String S)
    {
        return S[0];
    }
    
    //----KMP 模式匹配算法---
    //1.通过计算返回子串T的next数组;
    //注意字符串T[0]中是存储的字符串长度; 真正的字符内容从T[1]开始;
    void get_next(String T,int *next){
        int i,j;
        j = 1;
        i = 0;
        next[1] = 0;
        //abcdex
        //遍历T模式串, 此时T[0]为模式串T的长度;
        //printf("length = %d\n",T[0]);
        while (j < T[0]) {
            //printf("i = %d j = %d\n",i,j);
            if(i ==0 || T[i] == T[j]){
                //T[i] 表示后缀的单个字符;
                //T[j] 表示前缀的单个字符;
                ++i;
                ++j;
                next[j] = i;
                //printf("next[%d]=%d\n",j,next[j]);
            }else
            {
                //如果字符不相同,则i值回溯;
                i = next[i];
            }
        }
    }
    
    //输出Next数组值
    void NextPrint(int next[],int length)
    {
        int i;
        for(i=1;i<=length;i++)
            printf("%d",next[i]);
        printf("\n");
    }
    
    int count = 0;
    //KMP 匹配算法(1)
    //返回子串T在主串S中第pos个字符之后的位置, 如不存在则返回0;
    int Index_KMP(String S,String T,int pos){
        
        //i 是主串当前位置的下标准,j是模式串当前位置的下标准
        int i = pos;
        int j = 1;
        
        //定义一个空的next数组;
        int next[MAXSIZE];
        
        //对T串进行分析,得到next数组;
        get_next(T, next);
        count = 0;
        //注意: T[0] 和 S[0] 存储的是字符串T与字符串S的长度;
        //若i小于S长度并且j小于T的长度是循环继续;
        while (i <= S[0] && j <= T[0]) {
            
            //如果两字母相等则继续,并且j++,i++
            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 -1;
        }
        
    }
    
        //KMP算法调用
        StrAssign(s1,"abcababca");
        printf("主串为: ");
        StrPrint(s1);
        StrAssign(s2,"abcdex");
        printf("子串为: ");
        StrPrint(s2);
        Status = Index_KMP(s1,s2,1);
        printf("主串和子串在第%d个字符处首次匹配(KMP算法)[返回位置为负数表示没有匹配] \n",Status);
    
    

    KMP 算法优化

    假设主串S = aaaabcde,模式串T = aaaaax,在对 next数组求解,得到:

    next = [0, 1, 2, 3, 4, 5],在匹配的过程中,会出现下面情况:
    
    依次字符匹配,当匹配到主串 i=5, 模式串 j=5 时, b != a
    则,将 j 回溯到 j = next[j] = 4 的位置
    此时依然是 b != a,继续回溯,直到 j = 0
    这样前面的几次回溯匹配是没有必要的
    

    所以,我们可以对其进行优化,可以复用前面重复字符的next值,在回溯是时候直接回溯到正确的位置。减少不必要的匹配过程。例如下面的示例:

    假设 模式串T = ababaaaba,在求解 nextVal 数组时:
    
    当 j = 1,nextVal[1] = 0
    当 j = 2,第二个字符'b',第一个字符'a',不相等,nextVal[2] = next[2] = 1
    当 j = 3,第三个字符'a',第一个字符'a',相等,nextVal[3] = nextVal[1] = 0
    当 j = 4,第四个字符'b',其 next = 2,与第二个字符'b',相等,nextVal[4] = nextVal[2] = 1
    当 j = 5,第五个字符'a',其 next = 3,与第三个字符'a',相等,nextVal[5] = nextVal[3] = 0
    当 j = 6,第六个字符'a',其 next = 4,与第四个字符'b',不相等,nextVal[6] = next[6] = 4
    
    当 j = 7,其 next = 2,与第二个字符'b',不相等,nextVal[7] = next[2] = 2
    
    当 j = 8,其 next = 2,与第二个字符'b',相等,nextVal[8] = nextVal[2] = 1
    
    当 j = 9,其 next = 3,与第二个字符'a',相等,nextVal[9] = nextVal[3] = 0
    


    总结:

    在求解 nextVal 数组时:
    1. 默认nextVal【0】= 0
    2. T【i】= T【j】,且++i, ++j 后,T【i】依旧等于 T【j】,则 nextVal【i】 = nextVal【j】
    3. i=0,表示从头开始,i++,j++ 后,T【i】!= T【j】,则 nextVal = j
    4. T【i】= T【j】,且++i, ++j 后,T【i】!= T【j,则 nextVal = j
    5. T【i】!= T【j】,则将 i 退回到合理的位置, i = nextVal【i】
    

    KMP 算法优化实现

    void get_nextVal(String T,int *nextVal){
        int i,j;
        j = 1;
        i = 0;
        nextVal[1] = 0;
        while (j < T[0]) {
            if (i == 0 || T[i] == T[j]) {
                ++j;
                ++i;
                //如果当前字符与前缀不同,则当前的j为nextVal 在i的位置的值
                if(T[i] != T[j])
                    nextVal[j] = i;
                else
                //如果当前字符与前缀相同,则将前缀的nextVal 值赋值给nextVal 在i的位置
                    nextVal[j] = nextVal[i];
            }else{
                i = nextVal[i];
            }
        }
    }
    
    展开全文
  • 今天是算法数据结构专题第29篇文章,我们来聊一个新字符匹配算法——KMPKMP这个名字不是视频播放器,更不是看毛片,它其实是由Knuth、Morris、Pratt这三个大牛名字合称。老外很喜欢用人名来命名算法或者...

    本文始发于个人公众号:TechFlow,原创不易,求个关注


    今天是算法数据结构专题的第29篇文章,我们来聊一个新的字符串匹配算法——KMP。

    KMP这个名字不是视频播放器,更不是看毛片,它其实是由Knuth、Morris、Pratt这三个大牛名字的合称。老外很喜欢用人名来命名算法或者是定理,数学里就有一堆,什么高斯定理、欧拉函数什么的。但是中国人更倾向于从表意上来给一个概念命名,比如勾股定理、同余定理等等。之前觉得用人名命名很洋气,作者可以青史留名,后来想想这也是英文表意能力不足,很难用表意的方式起名的体现。

    扯远了,我们回到正题。


    应用场景


    在计算机领域当中字符串匹配其实是一个非常常见的问题,我们使用它的场景也多到不可计数。比如在一个已经打开的页面当中搜索关键词,再比如说git里面的代码变动的记录,以及论文的查重等等。在这些问题当中有些情况可能还好,比如说我们搜索一个关键词,因为关键词并不长,我们暴力枚举也不会特别耗时。但是在有些问题当中明显暴力匹配是无法胜任的,比如论文查重。一篇论文动辄上千词,要和库中的上万篇文章进行查重扫描,这当中的工作量可想而知。如果是暴力枚举算法那查重显然会查到天荒地老。

    所以早期的时候字符串匹配是一个难题,既然是难题那么显然就会有很多人来研究,也因此出了很多成果,很多大牛发表了字符串匹配的算法,其中KMP算法由于效率很高、实现复杂度低被应用得最广。到这里,我们就知道KMP算法是用来字符串匹配的。

    比方说我们有两个字符串,A串是:I hate learning English. B串是hate learning,很明显B串是A串的字符串。如果我们暴力枚举来判断的话,我们需要遍历A串当中的每一个起始位置是否能够完成匹配,那么复杂度显然是O(mn)O(mn)。通过KMP算法,我们可以在O(n)O(n)的时间内做到这点。

    著名的大佬matrix67在KMP算法的介绍博客当中有一句著名的骚话,当你有一个喜欢的MM,你可以委婉地问她:“假如你要向你喜欢的人表白的话,我的名字是你的告白语中的子串吗?”


    Next数组


    KMP算法的核心精髓只有一个就是Next数组,但是这个概念并不太容易理解,很多人学KMP放弃就是折戟在了Next这个数组上。

    我们先把Next数组是怎么来的放在一边,先来看下Next数组是用来干嘛的,它起作用的原理是什么,最后再来讨论Next数组怎么来的问题。根据我的理解,Next数组其实就是一个中途开始的机会,也就是当我们在枚举匹配的时候,发现了不匹配的情况,我们不是从头开始,而是从一个最大可能的中间结果开始。

    我们来看个例子:

    上图中上面的是A串,下面的是B串,我们在匹配的过程当中发现B串的前面几位都匹配上了,而在最后一位匹配失败。按照常规的做法,我们应该是移动到下一个位置从头开始匹配。但是这是非常浪费的,因为我们观察下可以发现失败位置的ABC和B串开头的ABC是可以构成匹配的

    我们之前失败的时候判断的是以C结尾的ABCDABC和B串的匹配,在这一次匹配失败之后,我们可以继续尝试匹配其他以C结尾的前缀串,比如ABC。这样我们就可以从中间状态开始,而节省了许多次不必要的枚举。但问题就来了,这个中间结果是怎么来的呢,我们怎么知道当下失败了上一个可行的中间结果是哪一个?

    对,没有错,前面说到的Next数组就是用来存储中间结果的。所以Next可以理解成下一次机会的意思,这样就好理解了。由于我们是在A串当中寻找B串,所以这个Next数组应该是针对B的,记录B中每一个位置如果匹配失败,它的前面一个可行的中间状态是哪一个。

    我们先写出来B的Next数组,等会再去研究它是怎么得到的。为了简化编码,我们假设字符串是从1位置开始的,所以我们在0的位置添加一个$符号作为占位符。对于大部分情况都是没有重来的机会的,失败了直接归零。而其中的A和B两个位置是有重来机会的,因为B的前缀当中出现了A和AB。所以如果在匹配ABD的时候失败了,我们还可以从AB处再次开始尝试匹配ABC。


    算法原理


    我们想象一根指针指向了B数组当中接下来要匹配的位置,如果匹配失败了,它就会跳转到Next数组当中记录的位置去,匹配成功了我们就向后移动一位。在有了Next数组之后,我们写出代码来真的很容易了:

    def kmp(var_str, template_str):
        # var_str即A串
        # template_str模式串即B串
        # 我们在两个字符串前加上了占位符
        var_str = '$' + var_str
        template_str = '$' + template_str
        next = generate_next(template_str)
        n, m = len(var_str), len(template_str)
        # head指向要匹配的位置的前一位
        head = 0
        for i in range(1, n):
            # 由于next数组很长,可能失败多次
            # 直到head+1的位置能匹配上或者head等于0
            while head > 0 and template_str[head+1] != var_str[i]:
                head = next[head]
            
            # 匹配上了则head变长一位
            if template_str[head+1] == var_str[i]:
                head += 1
            
            # 如果head长度等于B串了,则表示匹配成功
            if head == m - 1:
                return True
        
        return False
    

    对于A串中的每一个位置来说,我们都在B串当中遍历了每一个有可能构成匹配的前缀。所以说这个算法是可行的,一定可以获得解。另外一个问题是复杂度的问题,为什么我们用了两重循环,但仍然是O(n)O(n)的算法呢?

    其实很简单,因为while循环只会让head减小,而不会让head增加。head增加是在for循环里执行的,也就是说head最多增加n次。那么对应的while循环也就最多执行n次,因为head是非负的。所以while循环在整个for循环执行的过程当中最多执行了n次,整体执行的次数仍然是O(n)O(n)级别的而不是n2n^2级,当然是线性的算法。


    求解Next


    到这里,问题只剩下了一个,就是这个Next怎么来呢?

    其实我们在之前讲Next数组的使用的时候已经泄露天机了,我们再来看下上图,不知道大家能感觉到什么。

    后面一个A的Next值是1,也就是第一个A的下标,后面一个B的Next值是2,也就是第一个B的下标。换句话说第二个A能够和位置1的A匹配,后面的AB能和前缀的AB匹配。也就是说Next数组其实就是B数组自己和自己匹配的结果,我们在一开始的时候将整个Next数组全部置为0,然后依次递推迭代出所有的Next的值。

    我们在求解Next[i]的时候我们可以利用上Next[i-1]的值,因为Next[i-1]存储的是能够与B[i-1]匹配的前缀的结尾位置。如果B[Next[i-1]+1]等于B[i],那么说明Next[i] = Next[i-1] + 1。如果不等的话,我们可以用while循环来寻找能够匹配上的前缀。也就是说这是一个递推的过程,不过要注意一点我们计算Next数组要从2开始,因为对于1来说,Next[1]一定等于0。

    def generate_next(var_str):
        n = len(var_str)
        next = [0 for _ in range(n)]
        for i in range(2, n):
            # 用next[i-1]作为开始寻找能够匹配上的最长next[i]
            head = next[i-1]
            while head > 0 and var_str[head+1] != var_str[i]:
                head = next[head]
    		
            # 如果匹配上了,head+1
            if var_str[head+1] == var_str[i]:
                head = head + 1
            # 记录下来
            next[i] = head
        return next
    
    

    总结


    到这里,我们关于KMP算法的介绍就结束了,不知道大家看完之后感受如何,是不是有点蒙圈呢?

    其实蒙圈是正常的,我第一次学的时候足足看了好几遍才算是看明白。这毕竟是一个比较巧妙的算法,想要通过阅读一篇文章就完全学会还是比较困难的,最好的还是亲自动手实现一下试试。KMP算法我最大的感受就是如果你把整个算法的逻辑都串起来了,那么即是自己从头到尾推导一遍难度也不是很大(我就在面试当中推导过一次)。如果你没能把逻辑串起来,那么觉得难理解看不懂是正常的,你可能需要再读一遍或者是寻找一些其他的资料查漏补缺。

    今天的文章到这里就结束了,如果喜欢本文的话,请来一波素质三连,给我一点支持吧(关注、转发、点赞)。

    展开全文
  • 今天是算法数据结构专题第29篇文章,我们来聊一个新字符匹配算法——KMPKMP这个名字不是视频播放器,更不是看毛片,它其实是由Knuth、Morris、Pratt这三个大牛名字合称。老外很喜欢用人名来命名算法或者是...
  • 本文始发于个人公众号:TechFlow,原创不易,求个关注今天是算法数据结构专题第29篇文章,我们来聊一个新字符匹配算法——KMPKMP这个名字不是视频播放器,更不是看毛片,它其实是由Knuth、Morris、Pratt这三...
  • 单模式匹配 ...1,KMP算法的核心思想,与BM算法非常相近。假设主册是a,模式是b。再模式与主匹配过程中,当遇到不可匹配字符时候,找到一些规律,将模式往后多滑动几位,跳过肯定不会匹.
  • 今天是算法数据结构专题第29篇文章,我们来聊一个新字符匹配算法——KMPKMP这个名字不是视频播放器,更不是看毛片,它其实是由Knuth、Morris、Pratt这三个大牛名字合称。老外很喜欢用人名来命名算法或者是...
  • 数据结构 KMP算法

    2020-10-26 23:46:52
    串定义: 串是由零个或多个字符组成的有限序列 ...堆分配存储结构,char* 指向串的基地址 块链存储结构 代码实现基本操作 #define SSTRING_H_ #include<cstring> #include<iostream>
  • [数据结构与算法] 字符串的匹配算法(KMP算法) 标签: 实现strStr KMP算法 上一篇文章概述了一下BF算法以及缺点,这篇文章来说明一下KMP算法,对BF算法的优化。 如果你还不知道BF算法是什么: 点击我 先了解匹配...
  • KMP算法:主串不回溯,只有模式串的指针回溯 求next数组 当模式串的第 j 个字符匹配失败时,令模式串跳到 next[j],再继续匹配 串的前缀:包含第一个字符且不包括最后一个字符的子串 串的后缀:包含最后一个字符且不...
  • 串 定义:是由零个或者多个字符组成的有限序列。 串的顺序存储:a.每一个单元只存一个字符,称为非紧缩格式(存储密度小)。 b.... 串的连式存储: ...KMP算法与BF算法 题目: 【题意】 有两个字符串...
  • 数据结构与算法—复习:顺序表字符串的KMP算法实现 首先感叹一下KMP算法中求解next数组的算法之精妙: int* findNext(PSeqString s){ int* next = (int*)malloc(sizeof(s->n)); //分配适合大小的next数组空间 ...
  • python数据结构(三)——字符KMP算法的实现
  • 我们知道C语言里并没有字符串这种数据类型,而是利用字符数组加以特殊处理(末尾加'\0')来表示一个字符串,事实上数据结构里的串就是一个存储了字符的链表,并且封装实现了各种字符串的常用操作。  串的概念和定义...
  • 字符匹配KMP算法 KMP算法的流程 假设现在文本S匹配到 i 位置,模式P匹配到 j 位置 如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++,继续匹配下一个字符; 如果j != -1,且当前字符匹配...
  • KMP算法和BM算法KMP是前缀匹配和BM后缀匹配的经典算法,看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同前缀匹配是指:模式串和母串的比较从左到右,模式串的移动也是从 左到右后缀匹配是指:模式串和母...
  • 数学功底偏弱,最近花了1天时间才理解了用于字符匹配的KMP算法。 KMP算法是由 Knuth、Pratt 和 Morris 三个人同时发现的,因此取名为KMP,并不是什么功能性短语的缩写。该算法主要希望:“在字符匹配的过程中尽...
  • //此处为KMP算法的改进 //例如:S: aaaabcdef T: aaaaax //下标j 123456 void get_next2(string T, int *next){ int i, j; i = 1; j = 0; next[1] = 0; while(i ()) { if(0 == j || T[i] == T[j]) { ++i; ...
  • 数据结构 模式匹配 KMP算法

    千次阅读 2019-03-13 21:23:26
    数据结构】 串 KMP算法实现 KMP算法应用于串的模式匹配中 普通模式匹配算法在进行匹配时需要频繁对主串指针进行回溯,KMP算法通过将模式向右滑动一段距离的方式避免了主串的回溯,同时降低了算法复杂度 ,由...
  • 最近复习到字符串的地方...同时我借鉴了阮一峰老师的关于KMP算法的介绍以及图文,在最后补上我在网上学习的实现的比较的KMP算法 举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串
  • C++ | 数据结构——DS应用 KMP算法

    千次阅读 2018-10-12 16:13:51
    学习KMP算法,给出主串和模式串,求模式串在主串的位置 算法框架如下,仅供参考 输入 第一个输入t,表示有t个实例 第二行输入第1个实例的主串,第三行输入第1个实例的模式串 以此类推 输出 第一行...
  • 数据结构--KMP算法

    2018-12-10 16:36:10
    思路:定义一个主串的指针i 字串的指针j 当i和j下标的字符相同,i++;j++; 当不同时,从j=0开始找以j-1下标字符结尾的字符真子串,其长度为len, 与j-1下标开始回退len长度的字符真子串进行比较,如相同j=len; 那么...
  • 用字符 匹配字符 ,即判断 是否包含 , 表示字符 第 个字符next数组本身也是一个记录下标数组,所以会受到我们对于匹配项编码排序影响,理论上不连续编码也是可以,甚至不用数字编码都可行,但是为了...
  • 串 是由零个或多个字符组成的有限序列,一般记为S=‘a1a2...串的储存结构 1.定长顺序存储和堆存储结构 #define MAXLEN 255 //定长 typedef struct { char ch[MAXLEN]; int length; }SString; //堆存储 typedef struct
  • 大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的...
  • KMP算法用于模式字符匹配,因为没有提前预习,上课时听得云里雾里,后来回去看了一晚上,翻了一些网上讲解才理解了。我简单讲一下,我们在一字符A里搜索匹配另一段字符B时,思路最简单方法就是从第一位...
  • 1.在字符模式匹配的KMP算法中,求模式的next数组值定义如下: (1)当j=1时,为什么要取next[1]=0? (2)为什么要取max{k},k最大是多少? (3)其他情况是什么情况,为什么取next[j]=1? 解答: (1)当模式中的...

空空如也

空空如也

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

串的kmp算法数据结构

数据结构 订阅