字符串匹配算法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(第四版)