您现在的位置是:首页 > 编程语言 > 其他编程其他编程

KMP --算法竞赛(33)

2021-06-05 09:14:09其他编程人已围观

简介KMP比较难搞懂。本文用图解清晰地解释了KMP的思想,给出了模板代码,解析了几个经典例题。

前驱教材:《算法竞赛入门到进阶》 清华大学出版社
网购:京东 当当   作者签名书:点我
有建议请加QQ 群:567554289

本系列文章将于2021年整理出版。最近忙着赶稿,有一个多月没有发专题了。今天发一篇。一个多月后基本搞完初稿,再多发一些。

文章目录

  • 1. 朴素的模式匹配算法
  • 2. KMP算法
  • 3. 模板代码
  • 4. 例题
    • 4.1 最短循环节问题
    • 4.2 在S中删除所有的P
  • 【习题】

   KMP是字符串模式匹配算法,它包括预处理模式串和匹配两部分,复杂度为O(m + n),是此类算法能达到的最优复杂度。KMP的思路和编码很巧妙。

1. 朴素的模式匹配算法

  模式匹配(Pattern Matching)问题:在一篇长度为 n n n的文本 S S S中,找某个长度为 m m m的关键词 P P P。 P P P可能多次出现,都需要找到。
  最优的模式匹配算法复杂度能达到多好?由于至少需要检索文本 S S S的 n n n个字符和关键词 P P P的 m m m个字符,所以复杂度至少是 O ( m + n ) O(m + n) O(m+n)。
  先考虑朴素的模式匹配算法(暴力方法):从 S S S的第一个字符开始,逐个匹配 P P P的每个字符。例如 S = “ a b c x y z 123 ” , P = “ 123 ” S = “abcxyz123”,P = “123” S=“abcxyz123”,P=“123”。第1轮匹配, P [ 0 ] ≠ S [ 0 ] P[0] ≠ S[0] P[0]​=S[0],称为“失配”,后面的 P [ 1 ] 、 P [ 2 ] P[1]、P[2] P[1]、P[2]不用再比较。一共比较6 + 3 = 9次:前6轮比较 P P P的第1个字符,第7轮比较 P P P的3个字符 。
  (把P看成一个滑块,在轨道S上滑动,直到匹配。)

图1 朴素的模式匹配算法例1

  这个例子比较特殊, P P P和 S S S的字符基本都不一样。在每轮匹配时,往往第1个字符就对不上,用不着继续匹配 P P P后面的字符。复杂度差不多是 O ( n ) O(n) O(n),这已经是字符串匹配能达到的最优复杂度了。所以,如果字符串 S 、 P S、P S、P符合这个特征,暴力法是不错的选择。

  但是如果情况很坏,例如 P P P的前 m − 1 m-1 m−1个都容易找到匹配,只有最后一个不匹配,那么复杂度就退化成 O ( n m ) O(nm) O(nm)。例如 S = “ a a a a a a a a b ” , P = “ a a b ” S = “aaaaaaaab”,P = “aab” S=“aaaaaaaab”,P=“aab”。图2中 i i i指向 S [ i ] S[i] S[i], j j j指向 P [ j ] , 0 ≤ i < n , 0 ≤ j < m P[j],0 ≤ i < n,0 ≤ j < m P[j],0≤i<n,0≤j<m。第1轮匹配后,在 i = 2 , j = 2 i = 2,j = 2 i=2,j=2的位置失配。第2轮让 i i i回溯到1, j j j回溯到0,重新开始匹配。最后经过7轮,共匹配7×3 = 21次,远远超过上面例子中的9次。

图2 朴素的模式匹配算法例2

2. KMP算法

  KMP是一种在任何情况下都能达到 O ( n + m ) O(n + m) O(n+m)复杂度的算法。它是如何做到的?用KMP算法时,指向 S S S的 i i i指针不会回溯,而是一直往后走到底。与朴素方法比较,大大加快了匹配速度。

  在朴素方法中,每次新的匹配都需要对比 S S S和 P P P的全部 m m m个字符,这实际上做了重复操作。例如第一轮匹配 S S S的前3个字符 “ a a a ” “aaa” “aaa”和 P P P的 “ a a b ” “aab” “aab”,第二轮从 S S S的第2个字符 ‘ a ’ ‘a’ ‘a’开始,与和 P P P的第一个字符 ‘ a ’ ‘a’ ‘a’比较,这其实不必要,因为在第一轮比较时已经检查过这两个字符,知道它们相同。如果能记住每次的比较,用于指导下一次比较,使得 S S S的 i i i指针不用回溯,就能提高效率。
  如何让 i i i不回溯?分析两种情况。

(1)P在失配点之前的每个字符都不同
  例如 S = “ a b c a b c d ” , P = “ a b c d ” S = “abcabcd”,P = “abcd” S=“abcabcd”,P=“abcd”,第一次匹配的失配点是 i = 3 , j = 3 i = 3,j = 3 i=3,j=3。失配点之前的 P P P的每个字符都不同, P [ 0 ] ≠ P [ 1 ] ≠ P [ 2 ] P[0] ≠ P[1] ≠ P[2] P[0]​=P[1]​=P[2];而失配点之前的 S S S与 P P P相同,即 P [ 0 ] = S [ 0 ] 、 P [ 1 ] = S [ 1 ] 、 P [ 2 ] = S [ 2 ] P[0] = S[0]、P[1] = S[1]、P[2] = S[2] P[0]=S[0]、P[1]=S[1]、P[2]=S[2]。下一步如果按朴素方法, j j j要回到位置0, i i i要回到1,去比较 P [ 0 ] P[0] P[0]和 S [ 1 ] S[1] S[1]。但 i i i的回溯是不必要的。由 P [ 0 ] ≠ P [ 1 ] 、 P [ 1 ] = S [ 1 ] P[0] ≠ P[1]、P[1] = S[1] P[0]​=P[1]、P[1]=S[1]推出 P [ 0 ] ≠ S [ 1 ] P[0] ≠ S[1] P[0]​=S[1],所以 i i i没有必要回到位置1。同理, P [ 0 ] ≠ S [ 2 ] P[0] ≠ S[2] P[0]​=S[2], i i i也没有必要回溯到位置2。所以i不用回溯,继续从 i = 3 、 j = 0 i = 3、j = 0 i=3、j=0开始下一轮的匹配。

图3 失配点之前的P的每个字符都不同

  下面画出示意图。当 P P P滑动到左图位置时, i i i和 j j j所处的位置是失配点, S S S与 P P P的阴影部分相同,且阴影内部的 P P P的字符都不同。下一步直接把 P P P滑到 S S S的 i i i位置,此时 i i i不变、 j j j回到0,然后开始下一轮的匹配。

图4 P的每个字符都不同的滑动情况

(2)P在失配点之前的字符有部分相同
  再细分两种情况:

  1)相同的部分是前缀(位于 P P P的最前面)和后缀(位于 j j j的前面)。
  这里给出前缀和后缀的定义:字符串 A A A和 B B B,若存在 A = B C A = BC A=BC,其中 C C C是任意的非空字符串,称 B B B为 A A A的前缀;同理可定义后缀,若存在 A = C B A = CB A=CB, C C C是任意非空字符串,称 B B B为 A A A的后缀。从定义可知,一个字符串的前缀和后缀不包括自己。
  当 P P P滑动到下面左图位置时, i i i和 j j j所处的位置是失配点, j j j之前的部分与 S S S匹配,且子串1(前缀)和子串2(后缀)相同,设子串长度为 L L L。下一步把 P P P滑到右图位置,让 P P P的子串1和 S S S的子串2对齐,此时 i i i不变、 j = L j = L j=L,然后开始下一轮的匹配。注意,前缀和后缀可以部分重合。

图5 相同的部分是前缀和后缀

  2)相同部分不是前缀或后缀。
  下面左图, P P P滑动到失配点 i i i和 j j j,前面的阴影部分是匹配的,且子串1和2相同,但是1不是前缀(或者2不是后缀),这种情况与“(1)失配点之前的P的每个字符都不同”类似,下一步滑动到右图位置,即 i i i不变, j j j回溯到0。请读者自己分析。

图6 相同的部分不是前缀或后缀

  通过上面的分析可知,不回溯 i i i完全可行。KMP算法的关键在于模式 P P P的前缀和后缀,计算每个 P [ j ] P[j] P[j]的前缀、后缀,记录在 N e x t [ ] Next[] Next[]数组(也有写成 s h i f t shift shift或者 f a i l fail fail的)中, N e x t [ j ] Next[j] Next[j]的值等于 P [ 0 ] − P [ j − 1 ] P[0] - P[j-1] P[0]−P[j−1]这部分子串的前缀集合和后缀集合的交集的最长元素的长度。把这个最长元素称为“最长公共前后缀”。

  例如 P = “ a b c a a b ” P = “abcaab” P=“abcaab”,计算过程如下表,每一行的红色带下划线的子串是最长公共前后缀。

图7 最长公共前后缀

   N e x t [ ] Next[] Next[]只和 P P P有关,通过预处理 P P P得到。下面介绍一种复杂度只有 O ( m ) O(m) O(m)的极快的方法,它巧妙地利用了前缀和后缀的关系,从 N e x t [ i ] Next[i] Next[i]递推到 N e x t [ i + 1 ] Next[i+1] Next[i+1]。
  假设已经计算出了 N e x t [ i ] Next[i] Next[i],它对应 P [ 0 ] − P [ i − 1 ] P[0]-P[i-1] P[0]−P[i−1]这部分子串的后缀和前缀,见下面图8(1)所示。后缀的最后一个字符是 P [ i − 1 ] P[i-1] P[i−1]。阴影部分 w w w是最长交集,交集 w w w的长度为 N e x t [ i ] Next[i] Next[i],这个交集必须包括后缀的最后一个字符 P [ i − 1 ] P[i-1] P[i−1]和前缀的第一个字符 P [ 0 ] P[0] P[0]。前缀中阴影的最后一个字符是 P [ j ] , j = N e x t [ i ] − 1 P[j],j = Next[i]-1 P[j],j=Next[i]−1。

  图8(2)推广到求 N e x t [ i + 1 ] Next[i+1] Next[i+1],它对应 P [ 0 ]   P [ i ] P[0]~P[i] P[0] P[i]的后缀和前缀。此时后缀的最后一个字符是 P [ i ] P[i] P[i],与这个字符相对应,把前缀的 j j j也往后移一个字符, j = N e x t [ i ] j = Next[i] j=Next[i]。判断两种情况:
  (1)若 P [ i ] = P [ j ] P[i] = P[j] P[i]=P[j],则新的交集等于“阴影 w + P [ i ] w+ P[i] w+P[i]”,交集的长度 N e x t [ i + 1 ] = N e x t [ i ] + 1 Next[i+1] = Next[i]+1 Next[i+1]=Next[i]+1。如图(2)所示。

图8 若p[i] = p[j],从Next[i]推广到Next[i+1]

  (2)若 P [ i ] ≠ P [ j ] P[i] ≠ P[j] P[i]​=P[j],说明后缀的“阴影 w + P [ i ] w+P[i] w+P[i]”与前缀的“阴影 w + P [ j ] w+P[j] w+P[j]”不匹配,只能缩小范围找新的交集。把前缀往后滑动,也就是通过减小j来缩小前缀的范围,直到找到一个匹配的 P [ i ] = P [ j ] P[i] = P[j] P[i]=P[j]为止。如何减小 j j j?只能在 w w w上继续找最大交集,这个新的最大交集是 N e x t [ j ] Next[j] Next[j],所以更新 j ’ = N e x t [ j ] j’ = Next[j] j’=Next[j]。下图(2)画出了完整的子串 P [ 0 ]   P [ i ] P[0]~P[i] P[0] P[i],最后的字符 P [ i ] P[i] P[i]和 P [ j ] P[j] P[j]不等。斜线阴影 v v v是 w w w上的最大交集,下一步判断:若 P [ i ] = P [ j ’ ] P[i] = P[j’] P[i]=P[j’],则 N e x t [ i + 1 ] Next[i+1] Next[i+1]等于 v v v的长度加1,即 N e x t [ j ’ ] + 1 Next[j’]+1 Next[j’]+1;若 P [ i ] ≠ P [ j ’ ] P[i] ≠ P[j’] P[i]​=P[j’],继续更新 j ’ j’ j’。

图9 若p[i] ≠ p[j],更新j’ = Next[j]

  重复以上操作,逐步扩展 i i i,直到求得所有的 N e x t [ i ] Next[i] Next[i]。

3. 模板代码

  用下面的例题hdu 2087给出模板代码,包括 g e t N e x t ( ) 、 k m p ( ) getNext()、kmp() getNext()、kmp()两个函数。 g e t N e x t ( ) getNext() getNext()预计算 N e x t [ ] Next[] Next[]数组,是前面图解思路的完全实现,请对照注释学习这种巧妙的方法。 k m p ( ) kmp() kmp()函数在 S S S中匹配所有的 P P P,注意每次匹配到的起始位置是 s [ i + 1 − p l e n ] s[i+1-plen] s[i+1−plen],末尾是 s [ i ] s[i] s[i]。
  KMP算法的复杂度: g e t N e x t ( ) getNext () getNext()函数的复杂度为 O ( m ) O(m) O(m);匹配函数 k m p ( ) kmp() kmp()从 S [ 0 ] S[0] S[0]到 S [ n − 1 ] S[n-1] S[n−1]只走了一遍, S S S的每个字符只与 P P P的某个字符比较了1次,复杂度为 O ( n ) O(n) O(n);总复杂度为 O ( n + m ) O(n + m) O(n+m)。


剪花布条 hdu 2087
题目描述:一块花布条,上面印有一些图案,另有一块直接可用的小饰条,也印有一些图案。对于给定的花布条和小饰条,计算一下能从花布条中尽可能剪出几块小饰条。
输入:每一行是成对出现的花布条和小饰条。#表示结束。
输出:输出能从花纹布中剪出的最多小饰条个数。
Sample Input:
abcde a3
aaaaaa aa

Sample Output:
0
3


  本题代码套用了KMP的模板。找到的 P P P有很多个,而且可能重合,例如 “ a a a a a a ” “aaaaaa” “aaaaaa”包含了5个 “ a a ” “aa” “aa”。但在本题中,需要找到能分开的子串,即剪出不同的小饰条。这个问题容易解决,只需要在程序中加一句 i f ( i − l a s t > = p l e n ) if( i-last >= plen) if(i−last>=plen)进行判断即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
char str[N], pattern[N];
int Next[N];
int cnt;
void getNext(char *p, int plen){ //计算Next[1]~Next[plen]
    Next[0]=0; Next[1]=0;
    for(int i=1; i < plen; i++){  //把i的增加看成后缀的逐步扩展
        int j = Next[i];          //j的后移:j指向前缀阴影w的后一个字符
        while(j && p[i] != p[j])  //阴影的后一个字符不相同
            j = Next[j];          //更新j
        if(p[i]==p[j])   Next[i+1] = j+1;
        else             Next[i+1] = 0;
    }
}
int kmp(char *s, char *p) {         //在s中找p
    int last = -1;
    int slen=strlen(s), plen=strlen(p);
    getNext(p, plen);               //预计算Next[]数组
    int j=0;
    for(int i=0; i<slen; i++) {     //匹配S和P的每个字符
        while(j && s[i]!=p[j])      //失配了。注意j==0是情况(1)
             j=Next[j];             //j滑动到Next[j]位置
        if(s[i]==p[j])  j++;        //当前位置的字符匹配,继续
        if(j == plen) {             //j到了P的末尾,找到了一个匹配
           	//这个匹配,在S中的起点是i+1-plen,末尾是i。如有需要可以打印:
           	// printf("at location=%d, %s\n", i+1-plen,&s[i+1-plen]);
            //-------------------30--33行是本题相关
            if( i-last >= plen) {   //判断新的匹配和上一个匹配是否能分开
                cnt++;
                last=i;              //last指向上一次匹配的末尾位置
            }
            //-------------------
        }
    }
}
int main(){
    while(~scanf("%s", str)){      //读串
        if(str[0] == '#')  break;
        scanf("%s", pattern);      //读模式串
        cnt = 0;
        kmp(str, pattern);
        printf("%d\n", cnt);
    }
    return 0;
}

4. 例题

4.1 最短循环节问题


洛谷 P4391
题目描述:字符串 S 1 S1 S1由某个字符串 S 2 S2 S2不断自我连接形成,但是字符串 S 2 S2 S2未知。给出 S 1 S1 S1的一个长度为 n n n的片段 S S S,问可能的 S 2 S2 S2的最短长度是多少。例如给出 S 1 S1 S1的一个长度为8的片段 P = “ c a b c a b c a ” P = “cabcabca” P=“cabcabca”,求最短的 S 2 S2 S2长度,答案是3, S 2 S2 S2可能是 “ a b c ” 、 “ c a b ” 、 “ b c a ” “abc”、“cab”、“bca” “abc”、“cab”、“bca”等。


题解:求字符串 P P P的最短循环节,读者可能想不到和最长公共前后缀、KMP的 N e x t [ ] Next[] Next[]数组有关。下面讨论两种情况,请读者自己画图帮助理解。
  1) P P P由完整的 k k k个 S 2 S2 S2连接而成。则 N e x t [ n ] Next[n] Next[n]等于 k − 1 k-1 k−1个 S 2 S2 S2的长度,那么剩下的 n − N e x t [ n ] n- Next[n] n−Next[n]等于一个 S 2 S2 S2的长度。
  2) P P P由 k k k个完整的 S 2 S2 S2和1个不完整的 S 2 S2 S2连接而成。设 S 2 S2 S2长度为 L L L,不完整的部分长度为 Z Z Z。则 N e x t [ n ] = ( k − 1 ) L + Z , n − N e x t [ n ] = k L + Z − ( k − 1 ) L − Z = L Next[n] = (k-1)L+Z,n - Next[n] = kL+Z-(k-1)L-Z = L Next[n]=(k−1)L+Z,n−Next[n]=kL+Z−(k−1)L−Z=L就是答案。
  综合起来答案等于 n − N e x t [ n ] n- Next[n] n−Next[n]。本题例子 “ c a b c a b c a ” , n = 8 , N e x t [ n ] = 5 “cabcabca”,n = 8,Next[n] = 5 “cabcabca”,n=8,Next[n]=5,最长公共前后缀是 “ c a b c a ” “cabca” “cabca”,答案是 n − N e x t [ n ] = 3 n - Next[n] = 3 n−Next[n]=3。
  这一题可以帮助深入理解最长公共前后缀和 N e x t [ ] Next[] Next[]数组。

4.2 在S中删除所有的P


洛谷 P4824
题目描述:给定一个字符串 S S S和一个子串 P P P,删除 S S S中第一次出现的 P P P,把剩下的拼在一起,然后继续删除 P P P,直到 S S S中没有 P P P,最后输出 S S S剩下的部分。 S S S中最多有 1 0 6 10^6 106个字符。
  本题的麻烦之处在于,删除一个 P P P之后两端的字符串有可能会拼接出一个新的 P P P。例如 S = “ a b a b c c y ” , P = “ a b c ” S = “ababccy”,P = “abc” S=“ababccy”,P=“abc”,删除第一个 P P P后, S = “ a b c y ” S = “abcy” S=“abcy”,出现了一个新的 P P P,继续删除,得 S = “ y ” S = “y” S=“y”。


题解:在 S S S中找 P P P是典型的KMP算法。不过,如果每找到并删除一个 P P P后,就重组 S S S然后在新的 S S S上再做一次KMP,会超时。能不能在删除一个 P P P后,继续在原 S S S上匹配和删除,总共只做一次KMP?
  如果对KMP算法中 i 、 j i、j i、j指针的移动有深刻理解,本题的任务是能用一次KMP完成的。如图10所示,图(1)在 i = 2 , j = 2 i = 2,j = 2 i=2,j=2处失配。图(2)找到了一个匹配, i = 4 i = 4 i=4,在正常情况下, j j j应该回到0开始下一轮的匹配,但是这里让 j j j回到被删除的 P P P前面的值,即 i = 2 i = 2 i=2时的 j = 2 j = 2 j=2,然后直接与 i = 5 i = 5 i=5对比,这样就衔接上了被删除的 P P P前后的字符串。在这个过程中 S S S不用重组, i i i不用回溯,一共只做了一次KMP。

图10 删除P后衔接前后的字符

  编码时在正常KMP中加入两条:
  1)定义一个和 S S S一样大的数组记录每个字符对应的 j j j值,用于删除一个 P P P后 j j j回到P前面的值。
  2)用一个栈记录删除 P P P后的结果。每移动一次 i i i就把 S [ i ] S[i] S[i]进栈,若KMP匹配到一个 P P P,此时栈顶就是 P P P,把栈顶的 P P P弹出栈,相当于删除了这个 P P P。最后栈中留下的就是 S S S删除了所有 P P P的结果。

【习题】

Hdu:1686,1711,2222,2896,3065,3336,2594。
POJ:1961,2406。
洛谷:P3375,P3435,P2375,P3426,P3193。

文章来源:https://blog.csdn.net/weixin_43914593/article/details/117533364

Tags:KMP 

很赞哦! ()

随机图文

文章评论

留言与评论(共有 0 条评论)
   
验证码:

本栏推荐

站点信息

  • 文章统计247968篇文章
  • 浏览统计18356次浏览
  • 评论统计1个评论
  • 标签管理标签云
  • 统计数据:统计代码
  • 微信公众号:扫描二维码,关注我们