字符串匹配——KMP算法_字符串匹配算法

字符串匹配——KMP算法

​ 字符串匹配是计算机编程中最常使用到的基础算法之一。字符串匹配相关的算法很多，Knuth-Morris-Pratt（KMP）算法是最常用的之一。最近在学习KMP算法，学习了许多相关的博客，记录一下，以备日后不会写了回来看看。

​ KMP算法有两个要点：1）部分匹配 和next数组的计算；2）利用部分匹配表解决字符串匹配问题。

1、KMP算法原理

（1）原理

​ 给定两个字符串：文本串S="BBC ABCDAB ABCDABCDABDE"和模式串P="ABCDABD",要求找出模式串P是否是文本串S的子串。KMP算法解决这一问题的原理如下：

1）首先，文本串S="BBC ABCDAB ABCDABCDABDE"的第一个字符与模式串P="ABCDABD"的第一个字符进行比较。因为B与A不匹配，所以搜索词后移一位。

2）B与A不匹配，搜索词再往后移。

3）重复2）的操作，直到文本串有一个字符，与模式串的第一个字符相同为止。

4）比较文本串和模式串的下一个字符，还是相同。

5）重复4）的操作，直到文本串有一个字符，与模式串对应的字符不相同。或者到模式串的最后一个字符都相同为止。

6）此时，最自然的反应是将模式串整个后移一位，再从头逐个比较。这样的操作便是暴力枚举的方法，但是效率很差，因为需要把"对比位置"移到已经比较过的位置，重比一遍。

7）一个基本事实是，当空格与D不匹配时，其实前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了匹配效率。

8）那么如何保证搜索位置继续往后移的时候不会漏掉能够匹配成功的子串呢？可以针对模式串，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。

根据部分匹配值表可以获得模式串的next值数组。next 数组考虑的是除当前字符外的最长相同前缀后缀，将部分匹配值整体右移一位，然后初值赋为-1，如下表所示：

9）已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数：
$$移动位数=已匹配的字符数-对应的部分匹配值$$
移动位数=6-2=4，因此模式串向后移动4位，继续匹配。上面的公式等价于：
$$\begin{gathered} 移动位数=j-next[j] \\ 也等价于 \\ j=next[j] \end{gathered}$$
其中j为模式串中的匹配失败的字符下标。

10）因为空格与Ｃ不匹配，模式串还要继续往后移。这时，已匹配的字符数为2（"AB"），对应的"部分匹配值"为0。所以，移动位数 = 2 - 0，结果为 2，于是将模式串向后移2位。

11）因为空格与A不匹配，继续后移一位。

12）逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将模式串向后移动4位。

13）逐位比较，直到模式串的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将模式串向后移动7位，这里就不再重复了。

（2）C++代码

// KMP字符串匹配，函数返回一个数组，数组前n-1个元素是匹配成功的子串的起始位置，最后一个元素是匹配成功的子串数目
// 函数两个字符串参数，分别是文本字符串和模式串
vector<int> kmpSearch(string s,string p)
{
    int i=0,j=0;
    int lenS=s.length();
    int lenP=p.length();
    int cnt=0;
    vector<int> res;
    
    while(i<lenS && j<lenP)
    {	
        //如果j==-1或者匹配成功，继续匹配下一个字符
        if(j==-1 || s[i]==p[j])
        {
            i++;
            j++;
        }
        // 如果j!=-1并且匹配失败，i保持不变，j=next[j]，next[j]是模式串第j+1个元素的next值
        // 这相当于是文本串不变，模式串向右移动j-next[j]
        else
        {
            j=next[j];
        }
        if(j==lenP)
        {
            cnt++;
            res.push_back(i-j);
            j=next[j];
        }
    }
    res.push_back(cnt);
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

2、部分匹配表和next数组的计算

（1）原理

​ 首先，要了解两个概念：“前缀"和"后缀”。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。例如对于前文的模式串P=“ABCDABD”：

前缀：A、AB、ABC、ABCD、ABCDA、ABCDAB

后缀：D、BD、ABD、DABD、CDABD、BCDABD

模式串P="ABCDABD"的部分匹配表：

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。

上表是这样得到的：

• "A"的前缀和后缀都为空集，共有元素的长度为0；

• "AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；

• "ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；

• "ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；

• "ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；

• "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；

• "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

使用递推计算next:

对于P的前j+1个序列字符：

• 若p[k] == p[j]，则next[j + 1 ] = next [j] + 1 = k + 1；
• 若p[k ] ≠ p[j]，如果此时p[ next[k] ] == p[j ]，则next[ j + 1 ] = next[k] + 1，否则继续递归前缀索引k = next[k]，而后重复此过程。 相当于在字符p[j+1]之前不存在长度为k+1的前缀"p0 p1, …, pk-1 pk"跟后缀“pj-k pj-k+1, …, pj-1 pj"相等，那么是否可能存在另一个值t+1 < k+1，使得长度更小的前缀 “p0 p1, …, pt-1 pt” 等于长度更小的后缀“pj-t pj-t+1, …, pj-1 pj”呢？如果存在，那么这个t+1 便是next[ j+1]的值，此相当于利用已经求得的next数组（next [0, ..., k, ..., j]）进行P串前缀跟P串后缀的匹配。

（2）C++代码

vector<int> nextArrayGet(string p)
{
    int lenP=p.length();
    int k=-1;
    int j=0;
   	vector<int> next;
    next.push_back(-1);
    
    while(j<lenP-1)
    {
        //p[k]表示前缀，p[j]表示后缀
        if(k==-1 || p[k]==p[j])
        {
            j++;
            k++;
            next.push_back(k);
        }
        else
        {
            k=next[k];
        }
    }
    return next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

（3）next数组的优化

前面使用的next数组还存在一个小问题。这个问题不影响使用，但是依然存在无效的操作。

如果用之前的next 数组方法求模式串“abab”的next 数组，可得其next数组为{-1, 0, 0, 1}，当它跟下图中的文本串去匹配的时候，发现b跟c失配，于是模式串右移j - next[j] = 3 - 1 =2位。

右移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 ]]。如果出现了p[j] = p[ next[j] ]怎么办呢？如果出现了，则需要再次递归，即令next[j] = next[ next[j] ]。

vector<int> nextArrayGet(string p)
{
    int lenP=p.length();
    int k=-1;
    int j=0;
   	vector<int> next;
    int res[lenP];
    res[0]=-1;
    
    
    while(j<lenP-1)
    {
        //p[k]表示前缀，p[j]表示后缀
        if(k==-1 || p[k]==p[j])
        {
            j++;
            k++;
            //较之前next数组求法，改动在下面4行
            // p[j] != p[ next[j] ]时，和原来一样
            if(p[j]!=p[k])
            	res[j]=k;		//之前只有这一行
            
            //因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
            else
                res[j]=res[k];
        }
        else
        {
            k=res[k];
        }
    }
    for(int i=0;i<lenP;i++)
        next.push_back(res[i]);
    return next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

使用优化之后的next数组为{-1, 0, -1, 0}，进行匹配：

1）S[3]与P[3]匹配失败。

2）S[3]保持不变，P的下一个匹配位置是P[next[3]]，而next[3]=0，所以P[next[3]]=P[0]与S[3]匹配。

3）由于上一步骤中P[0]与S[3]还是不匹配。此时i=3，j=next [0]=-1，由于满足条件j==-1，所以执行“++i, ++j”，即主串指针下移一个位置，P[0]与S[4]开始匹配。最后j==lenP，跳出循环，输出结果i - j = 4（即模式串第一次在文本串中出现的位置），匹配成功，算法结束。

3、KMP算法字符串匹配demo

#include<iostream>
#include<vector>
#include<string>
using namespace std;

//next数组计算
vector<int> nextArrayGet(string p)
{
    int lenP=p.length();
    int k=-1;
    int j=0;
   	vector<int> next;
    int res[lenP];
    res[0]=-1;
    
    
    while(j<lenP-1)
    {
        //p[k]表示前缀，p[j]表示后缀
        if(k==-1 || p[k]==p[j])
        {
            j++;
            k++;
            //较之前next数组求法，改动在下面4行
            // p[j] != p[ next[j] ]时，和原来一样
            if(p[j]!=p[k])
            	res[j]=k;		//之前只有这一行
            
            //因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
            else
                res[j]=res[k];
        }
        else
        {
            k=res[k];
        }
    }
    for(int i=0;i<lenP;i++)
        next.push_back(res[i]);
    return next;
}

//KMP匹配
// KMP字符串匹配，函数返回一个数组，数组前n-1个元素是匹配成功的子串的起始位置，最后一个元素是匹配成功的子串数目
// 函数两个字符串参数，分别是文本字符串和模式串
vector<int> kmpSearch(string s,string p)
{
    int i=0,j=0;
    int lenS=s.length();
    int lenP=p.length();
    int cnt=0;
    vector<int> res;
    
    //计算next数组
    vector<int> next=nextArrayGet(p);
    
    while(i<lenS && j<lenP)
    {	
        //如果j==-1或者匹配成功，继续匹配下一个字符
        if(j==-1 || s[i]==p[j])
        {
            i++;
            j++;
        }
        // 如果j!=-1并且匹配失败，i保持不变，j=next[j]，next[j]是模式串第j+1个元素的next值
        // 这相当于是文本串不变，模式串向右移动j-next[j]
        else
        {
            j=next[j];
        }
        if(j==lenP)
        {
            cnt++;
            res.push_back(i-j);
            j=next[j];
        }
    }
    res.push_back(cnt);
    return res;
}

//主函数
int main()
{
    string s, p;
    cout<<"输入文本串："<<endl;
    cin>>s;
    cout<<"输入模式串："<<endl;
    cin>>p;
    
    vector<int> res=kmpSearch(s,p);
    if(res[res.size()-1]==0)
        cout<<"匹配失败\n";
    else
    {
        cout<<"匹配成功，文本串中存在 "<<res[res.size()-1]<<" 个模式串子串，所在位置分别为：\n";
        for(int i=0;i<res[res.size()-1];i++)
            cout<<res[i]<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101