数据结构与算法——字符串匹配问题(KMP算法)

了解KMP算法

KMP算法也是比较著名的模式匹配算法。是由D.E.Knuth,J.H.Morrs和VR.Pratt发表的一个模式匹配算法。可以大大避免重复遍历的情况。

KMP模式匹配算法原理

情况1:假设现在有一个主串S="abcdefgab";模式串T="abcdex";

如果使用暴风算法的话，前面五个字母完全相等，直到第六个字母"f"和"x"不相等。如下图：

image.png
接下来按照暴风算法，我们需要执行主串i=2，i=3，i=4，i= 5，i = 6的字母与子串T的首字母均相比较，均不相等即下图比较操作
i=2.png
i=3.png
i=4.png
i=5.png
i=6.png
按照暴风算法设计，我们执行过程就是这样，但是对于匹配的子串T来说，"abcdex"中的首字母"a"与后面的串"bcdex"的字母都不相等
那就是说既然"abcdex"中的首字母"a"与后面的串"bcdex"的字母都不相等，暴风算法中执行i=2，3，4，5的操作判断都是多余。
KMP算法就是利用这个已知信息，不把"搜索位置"移到已经比较过的位置，继续把它后移，这样就提高了效率。
理解KMP关键

• 前提：如果知道T串中的首字母"a"与T中后面的字符均不相等
• T串的第二位"b"与S串中的第二位"b"已经判断相等。
• 那么就意味着T串的首字符"a"没有必要与S串的第二个字符"b"去比较，这样就可以省略了i=2的操作比较。

• 同理T串中的前五位字符与S串中前五位分别相等，就可以省略了T串的首字符与主串S中i= 3，i= 4，i= 5的比较。直接由i=1和i=6的操作就可以。

  
  image.png
• 之所以会保留i= 6的判断是因为在1⃣️中T[6]!=S[6],尽管我们已经知道T[1]!=S[6]。但是不能断定T[1]一定不等于S[6]

情况2:假设现在有一个主串S="abcababca";模式串T="abcabx";

• 刚开始的判断，前五个字符完全相等。第六个字符不相等。如下图1

  
  图1.png

• 根据刚才的经验，T的首字符"a"与T的第二个字符"b",第三个字符"c"都不相等。所以不需要做判断，那么步骤2、3都是多余的

  
  2、3步骤.png
• 因为在T的首位"a"与T的第四位"a"相等，T的第二位"b"与T的第五位"b"相等；而且在第一次比较多时候，第四、五位都是比较过的也是相等，所以T的首位"a"与S的第四位"a"相等，S的第二位"b"与T的第五位"b"相等，所以第四、五部的比较也是多余的；
  4、5步骤.png
  也就是说，对于子串中与首字符相等的字符，也是可以省略一部分不必要的判断步骤：
  如下图，省略了T串中前两位与S串中第四五位的比较
  image.png
• 对比以上两个例子，会发现在执行1操作比较时，i的值是6，而 i = 2、3、4、5后，到i=6市，i的值又等于6.
• 所以在暴风匹配算法中，主串i的值是不断地回溯来完成的。
• 在刚刚的分析中，有很多不必要的回溯，所以KMP的算法就是不让不必要的回溯发生。
  既然i的值不能回溯，那考虑的变化就是J的值了。
  通过刚刚的分析了解，我们屡次提到T串的首字符与自身后面字符的比较。如果有相等的字符串，j的变化就会不相同。也就是说，j的变化与主串无关系，而是与T串是否有重复相关联。
  image.png
  如上图，由于T串中没有重复的字符，所以j的值由6变为1
  再如下图，由于T串中前缀“ab”与最后的“x”前的缀“ab”相等，所以j就由6变为了三
  image.png
  由此得出的规律：J的值多少取决于当前字符串之前的串前后缀相似度。
  image.png

KMP匹配算法中_next数组的推导

情况1:模式串中无任何字符重复

T = “abcdex”
j 123456
模式串 abcdex
next[j] 011111

解读

• 当j=1时，next[1] = 0;
• 当j=2时，j 由1到j-1范围内只有字符“a”，属于其他情况，next[2] = 1
• 当j=3时，j 由1到j-1范围内有字符“ab”，a与b不相等，属于其他情况，next[3] = 1
• 当j=4时，j 由1到j-1范围内有字符“abc”，显然“abc”不存在相等情况，属于其他情况，next[4] = 1
• 当j=5时，j 由1到j-1范围内有字符“abca”，显然“abcd”不存在相等情况，属于其他情况，next[5] = 1
• 当j=6时，j 由1到j-1范围内有字符“abcde”，显然“abcde”不存在相等情况，属于其他情况，next[6] = 1
  在例1情况下，模式T中不存在任何重复的字符，所以next数组，推演过程中符合第一种情况与第三种情况，因此next数组为{011111}

情况2:模式串中类似"abcabx"

T = "abcabx"
j 123456
模式串T abcabx
next[j] 011123

解读

• 当j=1时，next[1] = 0;
• 当j=2时，j 由1到j-1范围内只有字符“a”，属于其他情况，next[2] = 1
• 当j=3时，j 由1到j-1范围内有字符“ab”，a与b不相等，属于其他情况，next[3] = 1
• 当j=4时，j 由1到j-1范围内有字符“abc”，显然“abc”不存在相等情况，属于其他情况，next[4] = 1
• 当j=5时，j 由1到j-1范围内有字符“abca”，显然“abca”存在前缀"a"与后缀“a”相等，由于{P(2-1) = P(5 -2+1)},即P1 = P4，K = 2,next[5] = 2
• 当j=6时，j 由1到j-1范围内有字符“abcab”，“abcab”存在相等情况，属于第二种情况，即P1P3-1=P(6-3+1)P(6-1)，即P1P2 = P3P4 ,所以 K= 3,next[6] = 3
  在例2情况下，模式T中存在任何重复的字符，所以next数组，推演过程中符合第一种情况与第二种情况，因此next数组为{011123}

经验：如果前后缀一个字符相等，K的值是2，两个字符相等，K的值是3，n个相等K就是n+1；

情况3:模式串中类似"ababaaaba"

T = "ababaaaba"
j———————123456789
模式串T——— ababaaaba
next[j]————011234223

解读

• 当j=1时，next[1] = 0;
• 当j=2时，j 由1到j-1范围内只有字符“a”，属于其他情况，next[2] = 1
• 当j=3时，j 由1到j-1范围内有字符“ab”，a与b不相等，属于其他情况，next[3] = 1
• 当j=4时，j 由1到j-1范围内有字符“aba”，显然“aba”存在相等情况，属于第二种情况，next[4] = 2
• 当j=5时，j 由1到j-1范围内有字符“abab”，显然“abab”存在前缀"ab"与后缀“ab”相等，next[5] = 3
• 当j=6时，j 由1到j-1范围内有字符“ababa”，“ababa”存在前缀“aba”与后缀“aba”相等，所以K=4，next[6]= 4;
• 当j=7时，j 由1到j-1范围内有字符“ababaa”，“ababaa”存在前缀“a”与后缀“a”相等，所以K=2，next[7]= 2;
• 当j=8时，j 由1到j-1范围内有字符“ababaaa”，“ababaaa”存在前缀“a”与后缀“a”相等，所以K=2，next[8]= 2;
• 当j=9时，j 由1到j-1范围内有字符“ababaaab”，“ababaaab”存在前缀“ab”与后缀“ab”相等，所以K=3，next[9]= 4;
  根据之前的K求取的规则，可以得出K值，所以next数组为{011234223}
  需要注意的是
  image.png

情况4:模式串中类似"aaaaaaaab"

T = "aaaaaaaab"
j———————123456789
模式串T——— aaaaaaaab
next[j]————012345678

解读

• 当j=1时，next[1] = 0;
• 当j=2时，j 由1到j-1范围内只有字符“a”，属于其他情况，next[2] = 1
• 当j=3时，j 由1到j-1范围内有字符“aa”，前缀“a”与后缀“a”相等，所以K=2，next[3] = 2
• 当j=4时，j 由1到j-1范围内有字符“aaa”，前缀“aa”与后缀“aa”相等，所以K= 3，next[4] = 3
• 当j=5时，j 由1到j-1范围内有字符“aaaa”，显然“aaa”存在前缀"aaa"与后缀“aaa”相等，next[5] = 4
• 当j=6时，j 由1到j-1范围内有字符“aaaaa”，存在前缀“aaaa”与后缀“aaaa”相等，所以K=5，next[6]= 5;
• 当j=7时，j 由1到j-1范围内有字符“aaaaaa”，存在前缀“aaaaa”与后缀“aaaaa”相等，所以K=6，next[7]= 6;
• 当j=8时，j 由1到j-1范围内有字符“aaaaaaa”，存在前缀“aaaaaa”与后缀“aaaaaa”相等，所以K=7，next[8]= 7;
• 当j=9时，j 由1到j-1范围内有字符“aaaaaaaa”，存在前缀“aaaaaaa”与后缀“aaaaaaa”相等，所以K=8，next[9]= 8;
  根据之前的K求取的规则，可以得出K值，所以next数组为{012345678}

KMP模式匹配算法实现

next数组其实就是求解字符串要回溯的位置
假设，主串S= “abcababca”;模式串T=“abcdex”，由以上分析得出next数组为011111，next数组意味着当主串与模式串不匹配时，都需要从第一个的位置重新比较。

image.png

KMP算法之next数组求解

#include <stdio.h>
#include "stdio.h"
#include "stdlib.h"

#include "math.h"
#include "time.h"
#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];
}

void get_next(String T,int *next){
    int i ,j;
    i = 0;
    j = 1;
    next[1] = 0;
    //T[0]代表模式串的长度
    while (j<T[0]) {
        if (T[i] == T[j] || i == 0) {
            I++;
            j++;
            next[j] = I;
        }else{
            //回溯到原来的位置
            i = next[I];
        }
    }
}
//输出next的值
void next_print(int *next,int length){
    for (int i = 1; i <= length; i++) {
        printf(" %d",next[I]);
    }
    printf("\n");
}

KMP算法查找

int count = 0;
//返回子串T在主串S中的第pos个字符之后的位置，不存在则返回0
int Index_KMP(String S ,String T,int pos){
    int i = pos;
    int j = 1;
    //定义一个空的next数组
    int next[MAXSIZE];
    //T串的分析，得到Next数组
    get_next(T, next);
    count = 0;
    //S[0]和T[0]分别代表S和T串的长度
    while (i <= S[0] && j<=T[0]) {
        if (S[i]==T[j] || j==0) {
            I++;
            j++;
        }else{
            //如果不匹配时，j退回到合适的位置，i不变
            j = next[j];
        }
    }
    if (j>T[0]) {
        return  i- T[0];
    }else{
        return -1;
    }
}

KMP算法优化

KMP算法也是有缺陷的，比如主串S=“aaaabcde”,模式串T= “aaaaax”。next的数组就是012345；

image.png

当开始匹配时，当i= 5，j = 5时，我们发现字符"b"与字符“a”不相等，如上图，j = next[5] = 4;

image.png
image.png
image.png

由于T串的第二、三、四、五位置的字符都与首位“a”相等，那么可以用首位next[1]的值去取代与它相等的后续字符的next[j],那么next数组为{0,0,0,0,0,5};

KMP匹配模式next的数组优化

image.png
image.png
image.png
image.png

KMP_NextVal数组逻辑

在求解nextVal数组的5种情况

1. 默认nextval[1]=0;
2. T[i] == T[j]且++i，++j后依旧等于T[j],则nextval[i] = nextval[j]
   3.i = 0,表示从头开始i++，j++且T[i]!=T[j],则nextval[i] = j;
   4.T[i]==T[j],++i，++j后T[i]!=T[j]，则nextval[i] = j;
   5.当T[i]!=T[j]，表示不相等，则需要将i退回到合理位置，则i= next[i];

代码实现KMP_nextVal

void KMP_NextVal(String T ,int *next){
    int i,j ;
    i = 1;
    j = 0;
    next[1]=0;
    while (i<T[0]) {
        if (j==0 ||T[i] == T[j]) {
            ++i;
            ++j;
            if (T[i]!=T[j]) {
                next[i] = j;
            }else{
                next[i] = next[j];
            }
        }else{
            j = next[j];
        }
    }
    
}