精华内容
下载资源
问答
  • 求子串的KMP算法

    千次阅读 2015-10-05 12:14:32
    求子串的KMP算法 【题目】  给定两个字符串str和match,长度分别为N和M,实现一个算法,如果字符串str中含有子串match,则返回match在str中的开始位置,不含有则返回-1; 【举例】  str = "acbc" ,match = "bc", ...

    求子串的KMP算法

    【题目】

      给定两个字符串str和match,长度分别为N和M,实现一个算法,如果字符串str中含有子串match,则返回match在str中的开始位置,不含有则返回-1;

    【举例】

      str = "acbc" ,match = "bc", 返回2。

      str = "acbc", match = "bcc", 返回-1。

    【要求】

      如果match的长度大于str的长度(M>N),str必然不会含有match,可直接返回-1.但如果N>=M,要求算法复杂度为O(N)


    【解答】

    什么是KMP算法

      KMP算法是一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特--莫里斯--普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。


    字符串匹配的普通解法

      最普通的解法就是依次遍历str字符串的每一个字符,直到匹配match。

    举个例子:str="aaaaaaaaaaaaaaaaab",match="aaaab"。

    1、刚开始匹配从str[0]开始,str[0]=match[0] ... 直到str[4] != match[4],发现匹配失败,下一次从str[1]开始匹配

    2、从str[1]重新开始匹配,str[1] = match[0] ... 直到str[5] != match[4],又发现不匹配,下一次从str[2]开始匹配

    3、从str[2]重新开始匹配,同样到了str[6] != match[4]发现匹配失败,如此下去,直到从str[13]开始匹配,str[13] = match[0],str[14] = match[1]  ... str[17] = match[4],这时匹配成功,返回子串开始位置13。

    这样的匹配发现时间复杂度特别高,每次都得重新挨个字符匹配,前面已经匹配过的信息没有利用好,从每个字符出发时,匹配代价都可能是O(M),一共N个字符,那么时间复杂度就是O(N x M)。


    KMP算法可以快速匹配子串

    1、先解释一下解题中用到的几个名词,分别是前缀子串、后缀子串、nextArr数组。

      前缀子串:是在match字符串中match[i]之前的,必须以match[0]开头而且不包含match[i-1]的子串

      后缀子串:是在match字符串中match[i]之前的,必须以match[i-1]结尾而且不包含match[0]的子串

      nextArr数组:nextArr[i]的含义是在match[i]之前的字符串match[0..i-1]中,后缀子串和前缀子串的最大匹配长度,这个长度就是nextArr[i]的值,nextArr数组是从匹配字符串match中得出的。

    这里举例几个典型例子来形象的说明一下这3个名称的关系

      比如 match = "abc1abc1",求一下nextArr[7],match[7]='1'之前的子串是"abc1abc",那么前缀子串和后缀子串的最大匹配是"abc",也就是前缀子串是"abc",后缀子串是"abc"时匹配度达到最大,那么nextArr[7] = 3,这里前缀子串包含(a,ab,abc,abc1,abc1a,abc1ab),后缀子串包含(c,bc,abc,1abc,c1abc,bc1abc),我们取前缀子串和后缀子串中匹配度最大的"abc";

      再比如match = "aaaaaaab",求一下nextArr[7],match[7]='b'之前的子串是"aaaaaaa",那么前缀子串和后缀子串最大匹配是"aaaaaa",前缀子串和后缀子串都是"aaaaaa",那么nextArr[7] = 6;

      至于如何得到nextArr数组,我先介绍完KMP算法之后再进行说明,这里先假设已经得到nextArr数组。

    2、下面介绍如何加速str和match的匹配过程

      假设从str[i]字符位置出发,匹配到str[j]位置时发现与match[j-i]中的字符不一致,也就是说,str[i]与

    match[0]一样,直到str[j-1]与match[j-i-1]的字符都是匹配的,但是到了str[i] != match[j-i],匹配失败


      因为现在有match字符串的nextArr数组,nextArr[j-i]的值表示match[0..j-i-1]这一段字符串前缀与后缀的最长匹配。假设前缀是下图a区域这一段,后缀是下图b区域这一段,再假设a区域的下一个字符为match[k],如下图:


      此时nextArr[j-i]的值是前缀和后缀的最大匹配长度,那么nextArr[j-i] = k;下一次的匹配不会是像普通解法那样退回到str[i+1]位置重新开始与match[0]匹配,而是直接滑动到str[j]与match[k]进行匹配检查,如下图:


      此处有个疑问,为什么从match[k]开始匹配呢,match[0..k-1]的字符为什么不进行匹配了呢?看下图所示,

    图中str和match两个字符串匹配到A和B字符时发生匹配失败,那么c和b区域字符是相等的,而a和b是后缀字符和前缀字符的最长匹配字符串,也就是说a和b相等,同时,a和c也是相等的,a区域的下一个字符是C,当match滑动到A和C两个字符进行匹配时,其前面的c和a两个区域因为是相等的所以可以省略检查,这样我们对已经匹配过的字符进行了合理的利用,加快匹配效率。

      

      然而,为什么中间存在一部分"不用检查"区域呢,因为在这个区域中,从任何一个字符出发都肯定匹配不出match。其实这个问题的答案我们可以从nextArr[j-1]中得出结论,nextArr[j-i]的含义是在match字符串中,从

    match[0...j-i]前缀子串和后缀子串的最长匹配长度,此时在"不用检查"区域必然不存在一个字符,比b区域更大

    的区域出现,这时b和c区域已经是在str和match的匹配过的字符串中重复度最大的值,也就是nextArr数组的值,所以,在向右滑动过的区域中必然会匹配不出,可以直接略过从而向右滑动。


      从整个匹配过程分析可以看到,str的匹配位置是不退回的,match一直在向右滑动。如果在str中某个位置完全匹配出match,整个过程停止。否则match滑动到str最右侧也最终停止,所以滑动的最大长度是N,那么时间复杂度就是O(N),匹配过程getIndexOf方法的代码如下:

    public static int getIndexOf(String str, String match) {
    
    		// 如果str的长度n小于match的长度m,直接返回-1
    		if (str == null || match == null || str.length() < match.length()) {
    			return -1;
    		}
    
    		char[] ss = str.toCharArray();
    		char[] ms = match.toCharArray();
    		int si = 0;
    		int mi = 0;
    		int[] nextArr = getNextArr(ms);// 获得nextArr数组
    		while (si < ss.length && mi < ms.length) {
    			// 如果str和match中字符挨个相等,则同时向后移动
    			if (ss[si] == ms[mi]) {
    				si++;
    				mi++;
    			}
    			// 如果str和match中没有前缀相等的字符,也就是没有可以省略匹配的字符,则从match[0]开始重新挨个匹配
    			else if (nextArr[mi] == -1) {
    				si++;
    			}
    			// 如果str和match中遇到一个不相等的字符,且nextArr[mi]!=-1,说明有重复的字符,下次匹配就从
    			// match[k]开始,nextArr[mi]=k;
    			else {
    				mi = nextArr[mi];
    			}
    		}
    
    		return mi == ms.length ? si - mi : -1;
    	}


       接下来我们就来说一下如何快速得到match字符串的nextArr数组,并且证明得到nextArr数组的时间复杂度为O(M)。对match[0]来说,在它之前没有字符,所以nextArr[0]=-1;对match[1]来说,在它之前只有一个字符,

    但nextArr数组的定义要求任何子串的后缀不能包括第一个字符(match[0]),所以match[1]之前的字符串只有长度为0的后缀子串,所以nextArr[1]=0。

    之后对match[i](i>1)的求解,过程如下:

    1、因为是从左到右依次求解nextArr,所以在求nextArr[i]时,nextArr[0..i-1]的值已经求出。假设match[i]字符为下图中的A字符,match[i-1]为B字符,通过nextArr[i-1]的值可以知道B字符前的子串最长前缀和后缀的匹配区域,如图的m区域是前缀子串,n区域是后缀子串,字符C是m区域之后的一个字符,然后看字符C和字符B是否相等。

    2、如果字符C与字符B相等,那么A字符之前的字符串最长前缀(m区域+C字符)与后缀(n区域+B字符)匹配区域就是

    nextArr[i] = nextArr[i-1] + 1;

    3、如果字符C与字符B不相等,就看字符C之前的前缀和后缀匹配情况,假设字符C是第cn个字符(match[cn]),那么

    nextArr[cn]就是其最长前缀和后缀的匹配长度,如下图:

      在上图中,n1区域和n2区域分别是字符C之前的字符串最长匹配好后缀与前缀区域,这是通过nextArr[cn]的值确定的,m1区域是m区域最右边的长度和n2区域一样,因为m和n区域相等,所以m1和n2区域相等,那么m1和n1区域也相等,字符D是n1区域后的一个字符,接下来比较字符D和字符B是否相等。

    (1)、如果相等,那么字符A的前缀子串就是 n1区域+D字符,后缀子串就是 m1区域+B字符,则nextArr[i] = nextArr[cn] + 1;

    (2)、如果不相等,就跳到字符D,寻找D的前缀子串和后缀子串,与字符C一样,如此循环,这样每一步都有一个字符与字符B进行比较,如果有相等的情况出现,那么nextArr[i]的值就可以确定;

    4、如果跳到了最左边的位置(match[0]),此时match[0] = -1;说明字符A之前的字符串不存在重复的字符,则令

    nextArr[i] = 0。这样下去就可以得出nextArr数组值,求解代码getNextArr代码如下:

    public static int[] getNextArr(char[] ms) {
    
    		// 如果ms长度就一个字符,直接返回-1
    		if (ms.length == 1) {
    			return new int[] { -1 };
    		}
    		int[] nextArr = new int[ms.length];
    		nextArr[0] = -1;// match[0]之前没有字符
    		nextArr[1] = 0;// match[1]之前只有一个字符,后缀子串长度是0
    		int pos = 2; // 从match[2]开始
    		int cn = 0;
    		while (pos < nextArr.length) {
    			// 如果match[cn]和match[pos-1]相等,那么nextArr[i] = nextArr[i-1] + 1
    			//  nextArr[i-1]=cn,那么nextArr[i]=cn +1;
    			if (ms[pos - 1] == ms[cn]) {
    				nextArr[pos++] = ++cn;
    			} 
    			//cn>0,还没有循环到最左侧,继续比较nextArr[cn];
    			else if (cn > 0) {
    				cn = nextArr[cn];
    			}
    			//直到cn==1,没有重复的字符,那么nextArr[pos] = 0;
    			else {
    				nextArr[pos++] = 0;
    			}
    		}
    
    		return nextArr;
    	}







    展开全文
  • KMP算法 详细的介绍的了字符串的KMP算法,并且里面有KMP算法的源代码。
  • 匹配字符串的KMP算法

    2016-09-13 17:27:39
    KMP算法,next数组

    如果要学KMP算法,就要先知道next数组,什么是next数组呢?举个例子:字符串“abcabc”,就是这个字符串的第i个字符前面的字符(不包括第i个本身)是否存在前缀和后缀相同的情况,如果存在,前缀或者后缀的长度就是next[i]的值,这句话后几个字不好理解。就是abcdab这个字符串,前缀是ab,后缀也是ab,这就叫做前缀和后缀相同。

    求解“abcabc”的next数组

    1. 再次说明一下什么是next数组
      • next[0]也就是a之前的字符串是否存在前缀和后缀相同的情况,我们一眼就看出来,他前面就没有字符串,我们约定next[0]=-1;
      • next[1]也就是b之前的字符串是否存在前缀和后缀相同的情况,我们一眼就看出来,他前面只有一个a,我们约定next[1]=0;
      • next[2]也就是c之前的字符串是否存在前缀和后缀相同的情况,他前面是ab,所以next[2]=0;
      • next[3]也就是a之前的字符串是否存在前缀和后缀相同的情况,他前面是abc,所以next[3]=0;
      • next[4]也就是b之前的字符串是否存在前缀和后缀相同的情况,他前面是abca,这个字符串有一个前缀后缀一样,就是那个a,所以next[4]=1;
      • next[5]也就是c之前的字符串是否存在前缀和后缀相同的情况,他前面是abcab,这个字符串有一个前缀后缀一样,就是那个ab,所以next[4]=2;
    2. 这个数组上面咱们是用肉眼看到的,下面咱们用代码展现出来怎么求一个字符串的next数组:
      • 如果next[j]=k;表示是这个字符串从p0到pk-1等于pj-k到pj-1
      • 对于next[j+1]而言,需要满足p0到pk等于pj-k到pj,是否存在这个k值?
      • 因为p0到pk-1等于pj-k到pj-1,所以我们只需要比较pj到pk是否相等。
        private static int[] getNext(String pattern) {
            int[] next = new int[pattern.length()];
            next[0] = -1;
            int j = 0, k = -1;
            while (j < pattern.length() - 1) {
                if (k == -1 || pattern.charAt(j) == pattern.charAt(k)) {
                    j++;
                    k++;
                    next[j] = k;
                }
                else {
                    k=next[k];
                }
            }
            return next;
        }
    

    如果好好看了上面分析的那几句话,这个算法还是很好理解的,k代表的就是上一步的next数组的值
    这其实并不是真正的next数组,还有待改进,改进后的next数组讲完KMP之后再说。
    这是第一次匹配:
    这里写图片描述
    如果用BF算法第二次从第二个开始就好了,KMP算法则不是,这会next数组的用途就发挥了,匹配串的角标五个开始失败的,next[5]等于2,所以接下来从匹配串的第一个字母对应着S2开始匹配,通过next数组知道前两个不用比较,直接比较T2和S5。也就是下面这幅图:
    这里写图片描述
    上面那段话你可能不理解,直接看代码就好了,KMP算法:

    private static int indexOf(String target, String pattern) {
            int next[] = getNext(pattern);
            int targetLength = target.length();
            int patternLength = pattern.length();
            int i = 0, j = 0;// 分别为目标串和模式串的下标
            while (i < targetLength && j < patternLength) {
                if (target.charAt(i) == pattern.charAt(j)) {
                    i++;
                    j++;
                } else {
                    j = next[j];
                    // 判断剩下的够不够长
                    if (targetLength - i + 1 < patternLength - j + 1) {
                        break;
                    }
                }
            }
            if (j == patternLength) {//匹配成功
                return i - j;
            } else {
                return -1;
            }
        }

    下面解决最后一个问题:优化后的next数组,
    那字符串abcabc来举例
    next[5]是等于2的,因为前面的字符串是abcab。假如说拿着他和abcabdabcabc来比较。第一次比较的是abcabd发现角标为五时对不住,按照上面的KMP算法,因为next[5]是2,所以下一次匹配是拿着abcabc中的第一个c和abcabdabcabc目标串的角标为5的字符d比较,明显因为第一次比较的时候就知道目标串的角标为5的字符不是c了。所以这是个例外,也就是next数组的应该有话的地方,就是next[j]和next[k]相等的时候应该特殊处理。

    private static int[] getNext(String pattern) {
            int[] next = new int[pattern.length()];
            next[0] = -1;
            int j = 1, k = -1;//knext[0]的值,每循环一次就是上一步的next[k]的值
            while (j < pattern.length() - 1) {
                if (k == -1 || pattern.charAt(j) == pattern.charAt(k)) {
                    j++;
                    k++;
                    if (pattern.charAt(j) == pattern.charAt(k)) {
                        next[j] = next[k];
                    }else {
                        next[j] = k;
                    }
    
                }
                else {
                    k=next[k];
                }
            }
            return next;
        }

    这里的话我上面解释的next数组的定义就不对了。因为next数组真正的是为KMP算法服务的,不是一个单独的事物。希望大家能懂。

    展开全文
  • 首先,KMP算法使字符匹配中的优化算法,使原来的O(m*n)降到了O(m+n) 关于他的理解,我推荐先看视频,他讲的很清楚了。汪都能听懂的KMP字符匹配算法 然后从可视化方面理解,推荐看看如何更好的理解和掌握 KMP...

    KMP算法Python实现

    今天研究KMP算法,看来很多版本,有不同的语言写的,但是感觉越看越乱,最后自己试着写一份进行总结

    首先,KMP算法使字符串匹配中的优化算法,使原来的O(m*n)降到了O(m+n)

    关于他的理解,我推荐先看视频,他讲的很清楚了。汪都能听懂的KMP字符串匹配算法
    然后从可视化方面理解,推荐看看如何更好的理解和掌握 KMP 算法? - 佑子的回答 - 知乎容
    最后从代码层理解Searching for Patterns | Set 2 (KMP Algorithm)
    代码不要看太多别人的,我感觉好多人写的也有问题,我在自己运行处问题时,有看有些同学写的,被带到其他坑里了。。。
    最后记录代码

    
    '''
    先求next数组
    '''
    
    def next_list(pattern):
        next=[]
        pattern_list=list(pattern)
        j=0
        i=1
        for s in range(len(pattern)):
            #第一位一直是0
            if s==0:
                next.append(0)
            #看第i个和第j个字母是否相同,如果相同,则累加
            #同时i,j同时右移
            elif(pattern_list[i]==pattern_list[j]):           
                next.append(j+1)
                j+=1
                i+=1
            #如果不相同,则next为0,同时j也退回第一个位置,i继续前进一个位置
            else:
                next.append(0)
                j=0
                i=s+1
        print(next)
        return next
    
    next_list('ABABCABAB')      
    
    def kmp(text,pattern):
        #text的位置
        i=0
        #pattern的位置
        j=0
        next=next_list(pattern)
        if(not(text and pattern)):
            print('字符串为空,请输入字符串')
        elif(len(text)<len(pattern)):
            print('原字符串过小')
        elif(text==pattern):
            print('字符串一致')
        else:
    
            while( (i<len(text) )):
                print((text[i],pattern[j]))
                print(i,j)
                #如果相同,则进行下一个对比
                if( text[i]==pattern[j]):
                    i+=1
                    j+=1
                #判断是不是匹配完了
                if j==len(pattern):
                    print('从第{0}个位置开始匹配'.format(i-j))
                    j=next[j-1]
                #如果不匹配,则j反回到前一个字母对应的next
                elif i<len(text) and text[i]!=pattern[j]:
                    #我就是少了这个判断,一直有问题,就是在不匹配后的第二步,后面这个很关键
                    if j!=0:
                    #这个就是精髓了,如果不匹配,就去找第一个和这个匹配的字符串,然后在这个前面的匹配字符串
                    #的后一个字母拿出来,再与长text比较的第i个字母比较
                        j=next[j-1]
                    #如果j已经回到了0,则通过增加i,text移动到下一个字母
                    else:
                        i+=1
    
    
    # text = "ABABDABACDABABCABAB"
    # pattern = "ABABCABAB"            
    text='abxabcabcaby'
    pattern='abcaby'
    kmp(text,pattern)
    
    
    #output:
    next=[0, 0, 0, 1, 2, 0]
    
    
    ('a', 'a')
    0 0
    ('b', 'b')
    1 1
    ('x', 'a')
    2 0
    ('a', 'a')
    3 0
    ('b', 'b')
    4 1
    ('c', 'c')
    5 2
    ('a', 'a')
    6 3
    ('b', 'b')
    7 4
    ('c', 'c')
    8 2
    ('a', 'a')
    9 3
    ('b', 'b')
    10 4
    ('y', 'y')
    11 5
    从第6个位置开始匹配
    
    展开全文
  • 大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求...2、优化的KMP算法 3、应算法需要定义的next值 4、手动写出较短串的next值的方法 5、最难理解的、足足有5行的代码...

    大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、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行算法,应该很容易明白了!

    展开全文
  • 前一篇博客写是有关B
  • 串的KMP算法 和 正则匹配的方法

    千次阅读 2008-11-12 20:09:00
    /*正则表示是用来匹配目的中是否含有正则式一种方法,对于正则式regexp,目的test,先定义正则匹配原则:c 匹配目的字符. 匹配任意字符* 匹配0个或多个此字符前一个字符例如: regexp:A. test...
  • BF算法的思想,就是一个字符一个字符的比较,如果不成功,就回溯到最开始第一个匹配成功的字符位置,从下一个字符开始从新进行匹配操作 (2)KMP算法: (2.1)构造Next数组的函数: (2.2)查找字符串的KMP算法实现...
  • 了解顺序表前提就是知道什么是线性表,线性表概念非常简单,就是除了头和尾元素之外所有元素都有一个前驱和一个后继,满足这样要求我们基本上都可以定义为线性表。 那么线性表我们在这里会讲述其中两种...
  • kmp算法是一种改进字符匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是根据给定模式W1,m,定义一个next函数。next函数...
  • 王道书和 KMP 算法内容优化,对考研kmp算法的详细讲解和习题。
  • 字符KMP算法

    2019-07-18 16:13:00
    ,但是当母串非常长而且字串在母串的靠后一部分的时候,就很容易TLE,因此就引出了KMP算法,此算法可以利用之前进行匹配时候得到的信息 来影响下一次匹配。然后我们开始学习KMP 第一步了解KMP算法:...
  • 以前计算机刚被发明时候,主要作用是做一些科学和工程计算工作,科学家发明计算机时候压根儿不可能想到后人还可以用来KMP。刚开始计算机都是处理数值工作,后来引入了...在分享KMP算法之前,我们先看一...
  • ——KMP算法

    千次阅读 2018-09-26 15:06:39
    串——KMP算法 如果我们要去找一个单词在一篇文章(相当于一个大字符串)中的定位,这种子串的定位操作通常称做串的模式匹配,是串中最重要的操作之一。 1、朴素模式匹配 按照通常的思路,要在一个长的字符串中找到...
  • 字符匹配KMP算法

    2020-05-12 19:40:30
    BF算法每次匹配失败时,模式串的游标都要置为0。 KMP算法匹配失败时,利用next数组找到模式串游标需要指向的位置。 ** 难点** :next数组的产生。 另外需要了解前缀后缀,真前缀真后缀的概念 ** 方法1:暴力(等价于...
  • 字符匹配 KMP算法

    2020-12-17 11:42:41
    KMP算法减少了很多不必要的比较操作,通过已经匹配主串的前缀中的最长可匹配后缀和模式串中的最长可匹配前缀使得模式串的快速移动。时间复杂度可达O(n + m) 【n,m分别是主串和模式串的长度】 next数组 算法的关键是...
  • 字符KMP算法

    2020-12-08 18:35:17
    KMP算法由Knuth、Morris和Pratt 提出字符匹配算法; MKP算法核心则是前缀表构建,关于前缀表如何去计算?很多资料在构建前缀表描述中很是简略,对于初学者很难搞懂前缀表到底是怎么计算出来。 为什么...
  • 字符匹配 KMP 算法

    2018-10-14 09:33:38
    KMP算法是 BF(Brute Force) 算法一种改进算法,是一种较为高效字符匹配算法。 相比 BF 暴力匹配算法,KMP 算法思想是利用已匹配信息,使得能够不发生回溯,也就是当发生不匹配时,文本(source)位置...
  • 字符匹配是计算机基本任务之...许多算法可以完成这个任务,Knuth-Morris-Pratt算法(简称KMP)是最常用之一。它以三个发明者命名,起头那个K就是著名科学家Donald Knuth。 这种算法不太容易理解,网上
  • 字符KMP算法,重复子字符 普通方法,双指针逐个比较: class Solution { public: bool repeatedSubstringPattern(string s) { for(int i = 1; i * 2 <= s.size(); i++) { if(s.size() % i == 0) ...
  • 数据结构中讲到关于字符匹配算法时,提到朴素匹配算法,和KMP匹配算法。朴素匹配算法就是简单一个一个匹配字符,如果遇到不匹配字符那么就在源字符中迭代下一个...KMP算法kmp算法不是在源字符中下手,他是...
  • 单模式匹配 ...1,KMP算法的核心思想,与BM算法非常相近。假设主册是a,模式是b。再模式与主匹配过程中,当遇到不可匹配字符时候,找到一些规律,将模式往后多滑动几位,跳过肯定不会匹.
  • 力扣- - 最短回文KMP算法) 文章目录力扣- - 最短回文KMP算法)一、题目描述二、分析之KMP算法1.暴力法2.KMP算法3.next数组求法1:暴力查找最长前后缀4.next数组求法25.完整KMP代码三、题目分析四、代码 ...
  • 字符匹配的KMP算法

    2017-09-25 16:26:54
    好,那我们看看KMP算法是如何匹配字符串的KMP算法KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的...
  • KMP算法——串的朴素模式匹配算法的优化、KMP算法的优化什么是串的模式匹配朴素(简单)模式匹配算法KMP算法——串的朴素模式匹配算法的优化KMP算法优化——nextval数组 什么是串的模式匹配 串的模式匹配:在主串中...
  • 字符匹配是计算机的基本任务之一。 举例来说,有一个字符"BBC ABCDAB ...下面的的KMP算法的解释步骤,引用于http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html 1....

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,140
精华内容 5,256
关键字:

串的kmp算法