字符串匹配算法KMP

时间：2023-01-06 22:31:07

介绍主要分为以下3个方面：

  1. 算法来源
  2. next[]数组
  3. 部分匹配表：
  4. 总结

算法来源

关键字定义

  • 主串：str
  • 模式串：pat

Brute force

实现1


int search(char[] str, char[] pat ){
    int M = str.length;
    int N = pat.length;

// 这里的i指向已经匹配过的字符序列的开头
    for(int i=0;i<=N-M;i++){
        int j;
        for(j=0;j<M;j++)
        if(str[i+j]!=pat[j])
            break;
        if(j==M)
            return i; //找到匹配
    }
    return N;  //未找到匹配
}

实现2

int search(char[] str, char[] pat ){
    int M = str.length;
    int N = pat.length;

// 这里的i指向已经匹配过的字符序列的末端
    for(int i=0,j=0;i<N && j<M;i++){
        int j;
        if(str[i]==pat[j])
            j++;
        else{
            i-=j;
            j=0;
        }
    }
    if(j==M)
        return i-M; //找到匹配
    else
        return N;  //未找到匹配
}

实现3

//实现3是实现2的while循环版本

int search(char[] str, char[] pat ){
    int M = str.length;
    int N = pat.length;
    int i = 0;
    int j = 0;
    while(i<M&&j<N){
        if(str[i]==pat[j]){
            i++;
            j++;  //继续比较后面的字符
        }
        else{
            i=i-j+1; //指针后退重新开始匹配
            j=0;
        }
    }

    if(j==M)
        return i-M; //找到匹配
    else
        return N;  //未找到匹配
}

暴力字符串查找算法的最坏情况需要进行M(N-M+1)次比较，由于一般情况下N>>M，所以其时间复杂度为O(NM)。

Example

str: bacbababaabcbab
pat: abababca

第一趟：
bacbababaabcbab
- abababca

第二趟
bacbababaabcbab
 |-
 abababca
第三趟
bacbababaabcbab
  -   abababca
第四趟
bacbababaabcbab
   -    abababca
第五趟
bacbababaabcbab
    |||||-
    abababca
第六趟
bacbababaabcbab
     -      abababca
第七趟
bacbababaabcbab
      |||-
      abababca
......

以上是brute force的遍历过程。但有什么问题么？为什么会有KMP？

以第5趟为例，在主串中字符a和模式串中字符b不匹配的时候，我们确切的知道了主串a之前的部分信息，因为这部分信息是和模式串b之前的信息是匹配的，那么我们是否可以利用这些信息呢？

在brute force中，第五趟匹配失败后，指针i会回退到其第五趟开始位置的下一个位置，而j会回退到0。

其实第6趟比较以及第7趟的前三次比较都是可以省略的，因为我们确切的知道第五趟比较a之前的四项是baba,而模式串的前四项是abab，显然不匹配，可以省略。而a之前的三项是aba，模式串的前三项也是aba，所以它们也不需要比较，显然匹配，要比较的就是接下来主串的a和模式串的b。（我们是否可以直接到这一步呢？当然可以），我们发现指向主串的指针i可以不回退。不回退会漏掉一些符合匹配的情况么？当然不会。以下是原因：

这里以另一个例子更好的说明这个问题。
str: ababcabcacbab
pat: abcac

第三趟匹配（brute force）
ababcabcacbab
  ||||-
  abcac

我们发现，i=6 and j=4不匹配后又需要从i=3 and j=0开始匹配，然而i=3 and j=0;i=4 and j=0; i=5 and j=0这几次比较都是不必要的。因为从第三趟已匹配的部分看出，主串中i=4,i=5,i=6是”bca”，正是模式串j=1,j=2,j=3对应的字符。所以a无需和这三个字符比较，a和bc显然不相等，a和a显然相等，所以我们只需要进行i=6以及j=1的比较。

"="代表匹配,并且不需要比较
ababcabcacbab
     =-      abcac

以上解释可能不太清楚，更好的解释是：

  • abc和bca不匹配
  • ab和ca不匹配
  • a和a匹配

所以以上三种情况前两种不匹配，第三种开始匹配，都不需要再进行比较，指针i不需要回退，而且我们并没有漏掉一些可能的匹配。问题的就变成了（主串中已匹配的部分的后缀）与（模式串的前缀）的比较问题，而主串中已匹配的部分同样也是模式串中已匹配的部分，所以问题的核心就变成了（模式串发生不匹配位置）前面的（子串的前缀和后缀）的比较的问题了。

简单的介绍下前缀后缀的定义：
abcd的前缀是：a ab abc
abcd的后缀是：bcd cd d
前缀后缀都不包括完整的字符串本身。

指针不需要回退有什么优点呢？那当然是减少了不必要的比较（包括不匹配的比较和已匹配的比较）。此时的字符串查找算法需要比较的次数不会超过N+M，时间复杂度也就变成了O(N)。KMP就是利用了这种不需要指针回退的思想。

next[]数组

既然说到了KMP的核心思想是主串指针i不回退，那么当主串和模式串不匹配的时候，主串中的i应该和模式串中的哪个元素开始比较呢？这就是next[]数组的问题了。

当i与j不匹配的时候，j = next[j]，再进行i，与j的匹配。next[j]值是发生不匹配位置的j之间的子串的最长相匹配的前缀和后缀的长度。（如果索引从0开始的话，长度对应的索引值是第（长度+1）个字符）。

字符串匹配算法KMP

其中j=0代表模式串的第一个字符都不匹配，但-1这个位置并不存在，此时进行的操作是主串指针i+1。

next数组的求法

  1. next[0] = -1,next[1]=0
  2. 后面求解每一位next[j]的值时，根据j的前一位进行比较，令k=next[j-1]
  3. 将s[j-1]与s[k]比较：
    • 如果相等，则next[j] = k+1
    • 如果不相等，令k = next[k]，如k不等于-1，跳到（3）;否则,说明j之前的子串没有可匹配的前缀和后缀，next[j]=0。

至于为什么这么求？如下图：

字符串匹配算法KMP

假设现在我们要求next[位置4]，我们已知next[位置3]=位置2，next[位置2]=位置1。

  • 如果 （位置3=next[位置3]），那么next[位置4]=next[位置3]+1 = 位置2+1。
  • 如果不等于，那么为什么next[位置3]要和next[位置2]（位置1）相比较呢？这是因为位置3之前一定存在与位置1之前的子串相匹配的子串。这里是ab。（位置2之前的子串在位置3之前存在，而位置1之前的子串在位置2之前存在。）

求next[]数组的代码

void computeNext(char pat[],int next[]){
    int i = 0;
    int j = -1;
    next[0] = -1;
    while(i<pat.length-1){
        if(j==-1||pat[i]==pat[j]){ 
        //这里i++因为比较的是i，其比较结果用在next[i+1]的计算上
            i++; 
            j++;
            next[i]=j;
        }
        else{
            j = next[j];
        }
    }
}

部分匹配表

部分匹配表，是指模式串到当前字符为止的子字符串中前缀和后缀的最长匹配值。
索引0位置的是0，无匹配
索引1位置的是0，因为a作为ab的前缀，b作为ab的后缀，无匹配
索引2位置是1，因为a是aba的前缀和后缀
索引3位置是2，因为ab是abab的前缀和后缀
索引4位置是3，因为aba是ababa的前缀和后缀
……

char:  | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |

这就是部分匹配表。和next[]数组类似，只是从另一个角度。
在主串i指针和模式串j指针发生不匹配的时候，主串i指针保持不变，此时，模式串应该右移，使得j之前的子串的前缀挪到后缀的位置，也就是整个模式串右移（子串长度-前缀长度）的距离。这里的前缀长度就是value值。

ababaabcbab
||||-
abababca

如上例子，当主串中d与子串中a不匹配的时候，由于j之前的子串的前缀ab要挪到后缀ab的位置，所以右移距离为4-2 = 2。这里ab的长度2就是部分匹配表在模式串最后一个匹配位置对应的value值。
这里右移两位，相当于j值左移两位，其对应的索引位置就是next[j]。

求部分匹配表的代码

void computePartialTable(char pat[],int value[]){
    int i = 1;
    int j = 0;
    value[0] = 0;
    while(i<pat.length){
        if(pat[i]==pat[j]){ 
 //因为索引是从0开始，而value中记录的是前缀后缀匹配的长度，所以是j+1
             value[i] = j+1;
             i++;
             j++;
        }
        else{
            if(j==0){ 
                //说明此时当前字符与第一个字符不匹配
                value[i] = 0;
                i++;
            }
            else
                j = value[j-1]; 
        }
    }
}

//为什么在pat[i]!=pat[j]且j!=0的时候,j要等于value[j-1]呢？
//这和next[]数组的图片展示类似。

字符串匹配算法KMP

why j=value[j-1]。以求value[位置3]为例，pat[位置3] != pat[位置2]，然后 j = value[位置2] = 2，对应于位置1。为什么i和位置1开始比较，同样的理由:
这是因为位置3之前一定存在与位置1之前的子串相匹配的子串。这里是ab。（位置2之前的子串在位置3之前存在，而位置1之前的子串在位置2之前存在。）

总结

求next[]，还是求value[]，其实殊途同归。以模式串abababca为例。

char:  | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
next:  | -1| 0 | 0 | 1 | 2 | 3 | 4 | 0 |

以j=5发生不匹配为例，此时前面已经有5个字符匹配，根据value[4]=3，应该整个模式串右移5-3=2个位置，对应于j左移两个位置进行比较，5-2 = 3，也就是next[5]。

参考

The Knuth-Morris-Pratt Algorithm in my own words
数据结构（王道论坛）
Algorithms(第四版)

标签：

相关文章