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

    申明:此篇博文为转载博文,原博文地址:https://www.cnblogs.com/yjiyjige/p/3263858.html

    什么是KMP算法:

    KMP是三位大牛:D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的。其中第一位就是《计算机程序设计艺术》的作者!!

    KMP算法要解决的问题就是在字符串(也叫主串)中的模式(pattern)定位问题。说简单点就是我们平时常说的关键字搜索。模式串就是关键字(接下来称它为P),如果它在一个主串(接下来称为T)中出现,就返回它的具体位置,否则返回-1(常用手段)。

     

    首先,对于这个问题有一个很单纯的想法:从左到右一个个匹配,如果这个过程中有某个字符不匹配,就跳回去,将模式串向右移动一位。这有什么难的?

    我们可以这样初始化:

     

    之后我们只需要比较i指针指向的字符和j指针指向的字符是否一致。如果一致就都向后移动,如果不一致,如下图:

     

     

    A和E不相等,那就把i指针移回第1位(假设下标从0开始),j移动到模式串的第0位,然后又重新开始这个步骤:

     

    基于这个想法我们可以得到以下的程序:

    复制代码
     1 /**
     2 
     3  * 暴力破解法
     4 
     5  * @param ts 主串
     6 
     7  * @param ps 模式串
     8 
     9  * @return 如果找到,返回在主串中第一个字符出现的下标,否则为-1
    10 
    11  */
    12 
    13 public static int bf(String ts, String ps) {
    14 
    15     char[] t = ts.toCharArray();
    16 
    17     char[] p = ps.toCharArray();
    18 
    19     int i = 0; // 主串的位置
    20 
    21     int j = 0; // 模式串的位置
    22 
    23     while (i < t.length && j < p.length) {
    24 
    25        if (t[i] == p[j]) { // 当两个字符相同,就比较下一个
    26 
    27            i++;
    28 
    29            j++;
    30 
    31        } else {
    32 
    33            i = i - j + 1; // 一旦不匹配,i后退
    34 
    35            j = 0; // j归0
    36 
    37        }
    38 
    39     }
    40 
    41     if (j == p.length) {
    42 
    43        return i - j;
    44 
    45     } else {
    46 
    47        return -1;
    48 
    49     }
    50 
    51 }
    复制代码

    上面的程序是没有问题的,但不够好!(想起我高中时候数字老师的一句话:我不能说你错,只能说你不对~~~)

    如果是人为来寻找的话,肯定不会再把i移动回第1位,因为主串匹配失败的位置前面除了第一个A之外再也没有A了,我们为什么能知道主串前面只有一个A?因为我们已经知道前面三个字符都是匹配的!(这很重要)。移动过去肯定也是不匹配的!有一个想法,i可以不动,我们只需要移动j即可,如下图:

     

    上面的这种情况还是比较理想的情况,我们最多也就多比较了再次。但假如是在主串“SSSSSSSSSSSSSA”中查找“SSSSB”,比较到最后一个才知道不匹配,然后i回溯,这个的效率是显然是最低的。

     

    大牛们是无法忍受“暴力破解”这种低效的手段的,于是他们三个研究出了KMP算法。其思想就如同我们上边所看到的一样:“利用已经部分匹配这个有效信息,保持i指针不回溯,通过修改j指针,让模式串尽量地移动到有效的位置。”

     

    所以,整个KMP的重点就在于当某一个字符与主串不匹配时,我们应该知道j指针要移动到哪

     

    接下来我们自己来发现j的移动规律:

     

    如图:C和D不匹配了,我们要把j移动到哪?显然是第1位。为什么?因为前面有一个A相同啊:

     

    如下图也是一样的情况:

     

    可以把j指针移动到第2位,因为前面有两个字母是一样的:

     

    至此我们可以大概看出一点端倪,当匹配失败时,j要移动的下一个位置k。存在着这样的性质:最前面的k个字符和j之前的最后k个字符是一样的

    如果用数学公式来表示是这样的

    P[0 ~ k-1] == P[j-k ~ j-1]

    这个相当重要,如果觉得不好记的话,可以通过下图来理解:

     

    弄明白了这个就应该可能明白为什么可以直接将j移动到k位置了。

    因为:

    当T[i] != P[j]时

    有T[i-j ~ i-1] == P[0 ~ j-1]

    由P[0 ~ k-1] == P[j-k ~ j-1]

    必然:T[i-k ~ i-1] == P[0 ~ k-1]

    公式很无聊,能看明白就行了,不需要记住。

    这一段只是为了证明我们为什么可以直接将j移动到k而无须再比较前面的k个字符。

     

    好,接下来就是重点了,怎么求这个(这些)k呢?因为在P的每一个位置都可能发生不匹配,也就是说我们要计算每一个位置j对应的k,所以用一个数组next来保存,next[j] = k,表示当T[i] != P[j]时,j指针的下一个位置。

     

    很多教材或博文在这个地方都是讲得比较含糊或是根本就一笔带过,甚至就是贴一段代码上来,为什么是这样求?怎么可以这样求?根本就没有说清楚。而这里恰恰是整个算法最关键的地方。

    复制代码
     1 public static int[] getNext(String ps) {
     2 
     3     char[] p = ps.toCharArray();
     4 
     5     int[] next = new int[p.length];
     6 
     7     next[0] = -1;
     8 
     9     int j = 0;
    10 
    11     int k = -1;
    12 
    13     while (j < p.length - 1) {
    14 
    15        if (k == -1 || p[j] == p[k]) {
    16 
    17            next[++j] = ++k;
    18 
    19        } else {
    20 
    21            k = next[k];
    22 
    23        }
    24 
    25     }
    26 
    27     return next;
    28 
    29 }
    复制代码

    这个版本的求next数组的算法应该是流传最广泛的,代码是很简洁。可是真的很让人摸不到头脑,它这样计算的依据到底是什么?

    好,先把这个放一边,我们自己来推导思路,现在要始终记住一点,next[j]的值(也就是k)表示,当P[j] != T[i]时,j指针的下一步移动位置

    先来看第一个:当j为0时,如果这时候不匹配,怎么办?

     

    像上图这种情况,j已经在最左边了,不可能再移动了,这时候要应该是i指针后移。所以在代码中才会有next[0] = -1;这个初始化。

    如果是当j为1的时候呢?

     

    显然,j指针一定是后移到0位置的。因为它前面也就只有这一个位置了~~~

     

    下面这个是最重要的,请看如下图:

      

     

    请仔细对比这两个图。

    我们发现一个规律:

    当P[k] == P[j]时,

    有next[j+1] == next[j] + 1

    其实这个是可以证明的:

    因为在P[j]之前已经有P[0 ~ k-1] == p[j-k ~ j-1]。(next[j] == k)

    这时候现有P[k] == P[j],我们是不是可以得到P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]。

    即:P[0 ~ k] == P[j-k ~ j],即next[j+1] == k + 1 == next[j] + 1。

    这里的公式不是很好懂,还是看图会容易理解些。

     

    那如果P[k] != P[j]呢?比如下图所示:

     

    像这种情况,如果你从代码上看应该是这一句:k = next[k];为什么是这样子?你看下面应该就明白了。

     

    现在你应该知道为什么要k = next[k]了吧!像上边的例子,我们已经不可能找到[ A,B,A,B ]这个最长的后缀串了,但我们还是可能找到[ A,B ]、[ B ]这样的前缀串的。所以这个过程像不像在定位[ A,B,A,C ]这个串,当C和主串不一样了(也就是k位置不一样了),那当然是把指针移动到next[k]啦。

     

    有了next数组之后就一切好办了,我们可以动手写KMP算法了:

    复制代码
     1 public static int KMP(String ts, String ps) {
     2 
     3     char[] t = ts.toCharArray();
     4 
     5     char[] p = ps.toCharArray();
     6 
     7     int i = 0; // 主串的位置
     8 
     9     int j = 0; // 模式串的位置
    10 
    11     int[] next = getNext(ps);
    12 
    13     while (i < t.length && j < p.length) {
    14 
    15        if (j == -1 || t[i] == p[j]) { // 当j为-1时,要移动的是i,当然j也要归0
    16 
    17            i++;
    18 
    19            j++;
    20 
    21        } else {
    22 
    23            // i不需要回溯了
    24 
    25            // i = i - j + 1;
    26 
    27            j = next[j]; // j回到指定位置
    28 
    29        }
    30 
    31     }
    32 
    33     if (j == p.length) {
    34 
    35        return i - j;
    36 
    37     } else {
    38 
    39        return -1;
    40 
    41     }
    42 
    43 }
    复制代码

    和暴力破解相比,就改动了4个地方。其中最主要的一点就是,i不需要回溯了。

     

    最后,来看一下上边的算法存在的缺陷。来看第一个例子:

     

    显然,当我们上边的算法得到的next数组应该是[ -1,0,0,1 ]

    所以下一步我们应该是把j移动到第1个元素咯:

     

    不难发现,这一步是完全没有意义的。因为后面的B已经不匹配了,那前面的B也一定是不匹配的,同样的情况其实还发生在第2个元素A上。

    显然,发生问题的原因在于P[j] == P[next[j]]

    所以我们也只需要添加一个判断条件即可:

    复制代码
    public static int[] getNext(String ps) {
    
        char[] p = ps.toCharArray();
    
        int[] next = new int[p.length];
    
        next[0] = -1;
    
        int j = 0;
    
        int k = -1;
    
        while (j < p.length - 1) {
    
           if (k == -1 || p[j] == p[k]) {
    
               if (p[++j] == p[++k]) { // 当两个字符相等时要跳过
    
                  next[j] = next[k];
    
               } else {
    
                  next[j] = k;
    
               }
    
           } else {
    
               k = next[k];
    
           }
    
        }
    
        return next;
    
    } 
    复制代码

    好了,至此。KMP算法也结束了。

    很奇怪,好像不是很难的东西怎么就把我困住这么久呢?

    仔细想想还是因为自己太浮躁了,以前总是草草应付,很多细节都没弄清楚,就以为自己懂了。结果就只能是似懂非懂的。要学东西真的需要静下心来。

    展开全文
  • 数据结构KMP算法

    2018-10-18 17:39:06
    一. 首先求next值 例如: 模式串 a b a a b c a c  next值 0 1 1 2 2 3 1 2 next数组的求解方法是:第一位的next值为0,第二位的next值为1,后面求解每一位的next值时,根据前一位进行比较。...

    一. 首先求next值

    例如: 模式串 a b a a b c a c          

                 next值 0 1 1 2 2 3 1 2

    next数组的求解方法是:第一位的next值为0,第二位的next值为1,后面求解每一位的next值时,根据前一位进行比较。首先将前一位与其next值对应的内容进行比较,如果相等,则该位的next值就是前一位的next值加上1;如果不等,向前继续寻找next值对应的内容来与前一位进行比较,直到找到某个位上内容的next值对应的内容与前一位相等为止,则这个位对应的值加上1即为需求的next值;如果找到第一位都没有找到与前一位相等的内容,那么需求的位上的next值即为1。

    1.前两位必定为0和1。

    2.计算第三位的时候,看第二位b的next值,为1,则把b和1对应的a进行比较,不同,则第三位a的next的值为1,因为一直比到最前一位,都没有发生比较相同的现象。

    3.计算第四位的时候,看第三位a的next值,为1,则把a和1对应的a进行比较,相同,则第四位a的next的值为第三位a的next值加上1。为2。因为是在第三位实现了其next值对应的值与第三位的值相同。

    4.计算第五位的时候,看第四位a的next值,为2,则把a和2对应的b进行比较,不同,则再将b对应的next值1对应的a与第四位的a进行比较,相同,则第五位的next值为第二位b的next值加上1,为2。因为是在第二位实现了其next值对应的值与第四位的值相同。

    5.计算第六位的时候,看第五位b的next值,为2,则把b和2对应的b进行比较,相同,则第六位c的next值为第五位b的next值加上1,为3,因为是在第五位实现了其next值对应的值与第五位相同。

    6.计算第七位的时候,看第六位c的next值,为3,则把c和3对应的a进行比较,不同,则再把第3位a的next值1对应的a与第六位c比较,仍然不同,则第七位的next值为1。 7.计算第八位的时候,看第七位a的next值,为1,则把a和1对应的a进行比较,相同,则第八位c的next值为第七位a的next值加上1,为2,因为是在第七位和实现了其next值对应的值与第七位相同。

    二. nextval值的求法

    例如主串为“aaabaaaab”、  

            模式串为“aaaab”

    在计算nextval之前要先弄明白,nextval是为了弥补next函数在某些情况下的缺陷而产生的。 例如主串为“aaabaaaab”、模式串为“aaaab”那么,比较的时候就会发生一些浪费的情况:比较到主串以及模式串的第四位时,发现其值并不相等,据我们观察,我们可以直接从主串的第五位开始与模式串进行比较,而事实上,却进行了几次多余的比较。使用nextval可以去除那些不必要的比较次数。

    模式串       a b a a b c a c

    next值       0 1 1 2 2 3 1 2

    nextval值  0 1 0 2 1 3 0 2

    1.第一位的nextval值必定为0,第二位如果于第一位相同则为0,如果不同则为1。  

    2.第三位的next值为1,那么将第三位和第一位进行比较,均为a,相同,则,第三位的nextval值为0。

    3.第四位的next值为2,那么将第四位和第二位进行比较,不同,则第四位的nextval值为其next值,为2。

    4.第五位的next值为2,那么将第五位和第二位进行比较,相同,第二位的next值为1,则继续将第二位与第一位进行比较,不同,则第五位的nextval值为第二位的next值,为1。

    5.第六位的next值为3,那么将第六位和第三位进行比较,不同,则第六位的nextval值为其next值,为3。

    6.第七位的next值为1,那么将第七位和第一位进行比较,相同,则第七位的nextval值为0。

    7.第八位的next值为2,那么将第八位和第二位进行比较,不同,则第八位的nextval值为其next值,为2。

    三. KMP算法

    • KMP算法是用来处理字符串匹配的。换句话说,给你两个字符串,你需要回答,B串是否是A串的子串(A串是否包含B串)。例如”Today is Tuesday”.中是否包含”day”,在哪些位置包含。
    • 这个算法是由Knuth、Morris、Pratt三个提出来的,取了这三个人的名字的头一个字母。
    • 假如,A="abababaababacb",B="ababacb",我们来看看KMP是怎么工作的。我们用两个指针i和j分别表示,A[i-j+ 1..i]与B[1..j]完全相等。 也就是说,i是不断增加的,随着i的增加j相应地变化,且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前 j个字符(j当然越大越好),现在需要检验A[i+1]和B[j+1]的关系。当A[i+1]=B[j+1]时,i和j各加一;什么时候j=m了,我们就说B是A的子串(B串已经整完了),并且可以根据这时的i值算出匹配的位置。
    • 当A[i+1]<>B[j+1],KMP的策略是调整j的位置(减小j值)使得A[i-j+1..i]与B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配(从而使得i和j能继续增加)。我们看一看当 i=j=5时的情况。位置。

              i: 1 2 3 4 5 6 7 8 9 10

             A: a b a b a b a a b a b …

              B: a b a b a c b

               j: 1 2 3 4 5 6 7 8 9 10

    • 从上面的这个例子,我们可以看到,新的j可以取多少与i无关,只与B串有关。我们完全可以预处理出这样一个数组P[j],表示当匹配到B数组的第j个字母而第j+1个字母不能匹配了时,新的j最大是多少。P[j]应该是所有满足B[1..P[j]]=B[j-P[j]+1..j]的最大值。
    • 事实上,有可能j到了0仍然不能满足A[i+1]=B[j+1](比如A[8]="d"时)。因此,准确的说法是,当j=0了时,我们增加i值但忽略j直到出现A[i]=B[1]为止。

    算法实现:

    最后的j:=P[j]是 为了让程序继续做 下去,因为我们有 可能找到多处匹配。 这个程序或许 比想像中的要简单, 因为对于i值的不断 增加,代码用的是for循环。因此,这个代码可以这样形象地理解:扫描字符串A,并更新可以匹配到B的什么位置。

     

     

     

     

    展开全文
  • 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;
    }
    
    展开全文
  • 什么是模式匹配、常见模式匹配算法及C/C++/Java代码 详见...KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KM...

    什么是模式匹配常见模式匹配算法C/C++/Java代码 详见:https://blog.csdn.net/kjcxmx/article/details/82348917

    KMP算法是什么?

    先看看某度的解释。。

    KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。

    KMP算法的核心,也就是为什么可以如此的高效?关键就在于它Next数组的存在,有了Next数组就好比有一个滑动窗口,这样就避免了在匹配过程的主串中元素下标 i 不会发生回溯,也就是比较过程中的 i 始终是增加或不变的,这样就使得时间复杂度降低了,效率大大提高。

    如下例子:主串T为“BABABCAB”,模式串S为“ABCA”。

    A、见下图KMP.1开始进行Next数组的计算,首先把模式串S进行标号。(下面的例子中下标是从0开始的)

    B、见下图KMP.2中,分别写出每个字串的对应前缀,(当然也可以不写出,熟悉之后直接计算即可),最后一行也就是5号“A”对应的前缀为整个模式串。

    C、见下图KMP.3分别对各个子串的前后缀比较,算出最长字串的长度,写在对应左侧。如下文字分析

    第一行,只有一个字符“A”,没有前缀和后缀(前缀和后缀不能为串本身),所以为0

    第二行,串为“A B”,前缀为“A”,后缀为“B”,不匹配(一致),所以为0

    第三行,串为“A B A”,前缀为“A”和“A B”,后缀为“A”和“B A”,最大匹配长度为“A”=="A",所以为1

    第四行,串为“A B A B”,前缀为“A”和“A B”和“ABA”,后缀为“B”和“A B”和“BAB”,最大匹配长度为“A B”=="AB",所以为2

    第五行,串为“A B ABC”,前缀为“A”和“A B”和“ABA”和“ABAB”,后缀为“C”和“B ABC”和“ABC”和“BC”均不匹配,所以为0

    第六行,串为“A B ABCA”,前缀为“A”和“A B”和“ABA”和“ABAB”和“ABABC”,后缀为“A”和“CA”和“BCA”和“ABCA”和“BABCA”,最大匹配长度为“A”=="A",所以为1

    得出最大前后缀长度
    子串 AB ABA ABAB ABABC ABABCA
    前缀   A、B、AB A、AB、ABA A、AB、ABA、ABAB A、AB、ABA、ABAB、ABABC
    后缀   B、A、BA B、AB、BAB C、BC、ABC、BABC A、CA、BCA、ABCA、BABCA
    最大     A、B AB  
    最大长度

    D、见下图KMP.4我们得到了一个数列“001201”,并不是我们的Next数组,把这个数列不妨叫做MLength,对应写在子串下面。

    E、见下图KMP.5我们将MLength中最后一个元素即“1”删除,在开头增加一个元素“-1”,然后将整个MLength加一,即得到Next数组“011231”。到此我们便得到了Next数组,下面给出代码

    Java代码:

        /**
         * 获取next数组的值
         * @param ps 模式串(匹配串)
         * @return 
         */
        public static int[] getNext(String ps) {
            char[] p = ps.toCharArray();
            int[] next = new int[p.length];
            next[0] = -1;
            int j = 0;
            int k = -1;
            while (j < p.length - 1) {
               if (k == -1 || p[j] == p[k]) { //判断是否匹配
                   next[++j] = ++k;
               } else {
                   k = next[k];
               }
            }
            return next;
        }

    C/C++代码:

    void GetNext(char* p,int next[]){  
        int pLen = strlen(p);  
        next[0] = -1;  
        int k = -1;  
        int j = 0;  
        while (j < pLen - 1) {  
            if (k == -1 || p[j] == p[k]) {  //p[k]表示前缀,p[j]表示后缀  
                ++k;  
                ++j;  
                next[j] = k;  
            } else{  
                k = next[k];  
            }  
        }  
    }  

     

    优化KMP算法:

    其实上面的方法求Next数组,有一定的缺陷,匹配不成功有时候需要将模式串的j回溯。所以对于已经匹配过的了,就不必再重新回到开头重新匹配了。

    A、见下图KMP.6我们将在图KMP.5中修改,新增一行,分为两步给出NextVal数组。首先将第一个元素填为0

    1. 如果MLength[j]!=Next[j],则对应的填入Next中的数值
    2. 如果MLength[j]==Next[j],则对应的填入j-1对应的序号中的Next数值(这句话比较绕,多想想)这里的j是大于1的,即为j>1.这就解释了为什么首元素置零了。图中标的挺清楚,对应的符号一块看。

    给出下面代码:

    Java代码:

        /**
         * 优化后的获取next数组的值
         * @param ps 模式串(匹配串)
         * @return 
         */
        public static int[] getNextVal(String ps) {
            char[] p = ps.toCharArray();
            int[] next = new int[p.length];
            next[0] = -1;
            int j = 0;
            int k = -1;
            while (j < p.length - 1) {
               if (k == -1 || p[j] == p[k]) {
                   if (p[++j] == p[++k]) { //增加了一层判断,当两个字符相等时要跳过,否则赋值为k
                      next[j] = next[k];
                   } else {
                      next[j] = k;
                   }
               } else {
                   k = next[k];
               }
            }
            return next;
        }

    C/C++代码:

    void GetNextval(char* p, int next[]) {  
        int pLen = strlen(p);  
        next[0] = -1;  
        int k = -1;  
        int j = 0;  
        while (j < pLen - 1) {  
            if (k == -1 || p[j] == p[k]) { //p[k]表示前缀,p[j]表示后缀  
               ++j;  
               ++k;  
          if (p[j] != p[k]) //只需要改动在下面4行,添加一步判断  
                    next[j] = k;  
               else
                  next[j] = next[k];  
            } else {  
                k = next[k];  
            }  
        }  
    }

    KMP算法:

    Java代码:

        /**
         * 经典KMP算法
         * @param ts 主串(目标串)
         * @param ps 模式串(匹配串)
         * @return 
         */
        public static int KMPSearch(String ts, String ps) {
            char[] t = ts.toCharArray();
            char[] p = ps.toCharArray();
            int i = 0; // 主串的位置
            int j = 0; // 模式串的位置
            int[] next = getNext(ps);
            while (i < t.length && j < p.length) { //主要是这个循环
               if (j == -1 || t[i] == p[j]) { // 当j为-1时,要移动的是i,j也要归0
                   i++;
                   j++;
               } else {
                   // i不需要回溯 i = i - j + 1;
                   j = next[j]; // j回到指定位置
               }
            }
            if (j == p.length) {
               return i - j;
            } else {
               return -1;
            }
        }

    C/C++代码:

    int KmpSearch(char* s, char* p) {  
        int i = 0;  
        int j = 0;  
        int sLen = strlen(s);  
        int pLen = strlen(p);  
        while (i < sLen && j < pLen) {     
            if (j == -1 || s[i] == p[j]){//j = -1,或当前字符匹配成功(即S[i]==P[j])则后移
                i++;  
                j++;  
            } else {        
                j = next[j];  
            }  
        }  
        if (j == pLen)  
            return i - j;  
        else  
            return -1;  
    }

    结语:

    这样就完成了著名的KMP算法,算法中重要的是算法所蕴含的思想,理解了具体的算理也就能迁移到其他方面了。

    展开全文
  • KMP算法 如果我们要对下面的主串P和模式串P进行匹配 步骤一:i=3,j=3 模式串 “abab” 对应的 next 数组为-1 0 0 1(0 0 1 2整体右移一位,初值赋为-1),当模式串 P 和主串 S 进行匹配时,发现b跟c失配,于是模式...

    KMP算法

    PS:若不清楚KMP算法的运行过程,可参考 数据结构 —— KMP算法

    如果我们要对下面的主串P和模式串P进行匹配

    步骤一:i=3,j=3

    模式串 “abab” 对应的 next 数组为-1 0 0 1(0 0 1 2整体右移一位,初值赋为-1),当模式串 P 和主串 S 进行匹配时,发现b跟c失配,于是模式串 P 右移 j - next[ j ] = 3 - 1 =2位。

    在这里插入图片描述
    步骤二:i=3,j=1

    右移2位后,b又跟c失配。事实上,因为在上一步的匹配中,已经得知 P[3] = b,与 S[3] = c失配,而右移两位之后,让P[ next[3] ] = P[1] = b 再跟 S[3] 匹配时,必然失配。问题出在哪呢?

    在这里插入图片描述
    问题在于,我们应该避免出现 p[j] = p[ next[j] ]的情况。当P[j] != s[i] 时,下次匹配必然是 P[ next [ j ] ] 跟 S[i] 匹配,如果 P[j] = P[ next[ j ] ],必然导致后一步匹配失败(因为 P[j]已经跟 S[i]失配,然后你还用跟 P[j]等同的值 P[ next [ j ] ]去跟 S[i]匹配,很显然,必然失配),所以不能允许 P[j] = P[ next [ j ]]。

    由此可见,KMP 算法仍存在不足之处

    1. 没有利用到匹配失败时的信息(即P[j]),在使用 j=next[j] 进行回溯时进行了多余的计算

    因此,我们提出了改进的KMP算法,对 next 数组进行修正,得到 nextval 数组


    改进的KMP算法

    步骤一:i=3,j=3
    在这里插入图片描述
    因为 next[ 3 ]=1,故P[3] = P[ next[ 3 ] ] = P[1] = b ,next[3] 需要再次递归(因为当P[3] = P[ next[ 3 ] ]时,必然失配,所以要找到 next[ next [ 3 ] ]再进行匹配;如若继续失配,则继续往前寻找,直到找到不相等的P[next…]或到达临界点 j=-1),即令 nextval[3] = next[ next [ 3 ] ] = next[1] = 0,P[ next[ 1 ] ] = P[0] = a,P[3] ≠ P[ next[ 1 ] ],故对 P[3] 和 P[ next[ 1 ] ] 进行匹配

    步骤二:改进后变成了 i=3,j=0
    在这里插入图片描述

    此时,我们利用 nextval 解决了存在的问题


    求 nextval 数组

    上述内容介绍了改进的 KMP 算法的运行过程,那么接下来我们将介绍如何求出 KMP 算法中用到的 next 数组

    (前三步具体步骤省略,可参考 数据结构 —— KMP算法

    (1)寻找最长前缀后缀

    (2)得到最大长度表

    (3)求出 next 数组

    (4)求出 nextval 数组

    将 nextval 的初值赋为 -1
    在这里插入图片描述
    当 P[ j ] = P[ next[ j ] ] 时,只需让 nextval[ j ]赋值为 nextval [ next[ j ] ]。原因有两点:

    1. nextval 数组 时从下标0开始逐步往后求得的,所以在求 nextval[j]时,nextval [ next[ j ] ]必定已经存在
    2. nextval [ next[ j ] ]包含了前面的 nextval 的比较结果,因此无须再重复比较。

    参考文章

    https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html

    展开全文
  • kmp算法是子串配对的一种,并不是速度最快的,但是其算法思想非常巧妙。请允许我尝试用白话描述一下其思想,如果有什么不对的地方,恳请矫正。
  • 数据结构KMP算法

    2020-07-09 23:31:16
    数据结构里面的KMP算法,这是在VC6.0里面边写的,上传的是一个工程,可以直接使用的
  • // KMP字符串模式匹配算法 // 输入: S是主串,T是模式串,pos是S中的起始位置 // 输出: 如果匹配成功返回起始位置,否则返回-1 int KMP(PString S, PString T, int pos) { assert(NULL != S); assert(NULL != T); ...
  • KMP算法数据结构课上讲了两天,还是晕晕乎乎的,先把《算法笔记》里的笔记放上来吧~以后想起来再看 笔记文件过大,出不来可以先等等 笔记很占服务器带宽,访问速度应该挺慢的~ ...
  • 基本数据结构与算法笔记之--KMP算法 注:用于自己复习之用 KMP算法介绍: KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称...
  • 1、KMP算法求解什么类型问题? 字符串匹配。给你两个字符串,寻找其中一个字符串是否包含另一个字符串,如果包含,返回包含的起始位置。 2、完整的KMP算法 #include &amp;lt;bits/stdc++.h&amp;gt; ...
  • 字符串匹配KMP算法

    2019-02-26 11:35:54
    这两天帮同学看《算法与数据结构》试题,其中涉及到字符串匹配KMP算法,借机重新温习整理了一下,也算有了新的体会与感悟,希望能够讲得清楚。 从字符串匹配讲起 我们都说KMP算法是一种高效的字符串匹配算法,所以...
  • 数据结构kmp算法

    2019-07-02 00:10:39
    Knuth-Morris-Pratt 字符串查找算法,简称为 “KMP算法”,常用于在一个文本串S内查找一个模式串P 的出现位置,这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表,故取这3人的姓氏命名...
  • 代码 #include <iostream> using namespace std; typedef struct { char data[50];//存放串字符 int length;//存放串长 }SqString;//顺序串类型 ...s,char cstr[])//生成串,s为引用型参数 ... int ...
  • KMP算法中虽然计算了nextval的值,但我在此次并没有用到。 课程名称:数据结构 实验项目名称:串基本操作的实现 实验目的: 1.掌握串的模式匹配操作。 实验要求: 1、 分别使用BF和KMP算法完成串的模式...
  • 数据结构】 串 KMP算法实现 KMP算法应用于串的模式匹配中 普通模式匹配算法在进行匹配时需要频繁对主串指针进行回溯,KMP算法通过将模式向右滑动一段距离的方式避免了主串的回溯,同时降低了算法复杂度 ,由...
  • 本文将从7个方面对KMP算法以个人理解进行描述,参考书目:严蔚敏教授的《数据结构(C语言版)》 目录 KMP算法 1.什么是KMP算法? 2.经典字符串匹配算法。(老法子,效率低) 3.如何实现next数组? 4.Next...
  • KMP算法是我们数据结构串中最难也是最重要的算法。难是因为KMP算法的代码很优美简洁干练,但里面包含着非常深的思维。真正理解代码的人可以说对KMP算法的了解已经相当深入了。而且这个算法的不少东西的确不容易讲懂...
  • KMP算法是一种模式串匹配算法,即在主串S中找到模式串T第一次出现的首个字符在主串中的位置的一种相对高效的算法。为什么说KMP相对高效,这是因为在蛮力(BF)算法中如果当i!=j时,不仅仅j(模式串指针) 需要回退到...
  • 看了一晚上终于明白这个KMP算法是什么意思,果然只要是想学习,就能学会呀,谢谢这两篇博客 见网址http://www.cnblogs.com/SYCstudio/p/7194315.html和https://blog.csdn.net/f1033774377/article/details/82556438...
1 2 3 4 5 ... 20
收藏数 14,139
精华内容 5,655