Fork me on GitHub

字符串匹配算法

发表于 | 分类于 | | 本文总阅读量 次
如何在字符串数据中，检测和提取以字符串形式给出的某一局部特征，这类操作都属于串模式匹配（string pattern matching）范畴，简称串匹配。一般的，即对基于同一字符表的任何主串T(|T|=n)和模式串P(|P|=m)：判定T中是否存在某一子串与P相同，若存在（匹配），则报告该子串在T中的起始位置。
autoauto- 1. 问题描述auto- 2. 求解策略auto - 2.1. 暴力求解auto - 2.2. KMP算法autoauto

1. 问题描述

如何在字符串数据中，检测和提取以字符串形式给出的某一局部特征，这类操作都属于串模式匹配（string pattern matching）范畴，简称串匹配。一般的，即对基于同一字符表的任何主串$T(|T|=n)$和模式串$P(|P|=m)$：判定$T$中是否存在某一子串与$P$相同，若存在（匹配），则报告该子串在$T$中的起始位置。

一般串的长度都很大，但相对而言$n$更大，即满足$2<

1
2
3
T = "Now is the time for all good people to come."
P = "people"
T.indexOf(P) = 29.

2. 求解策略

2.1. 暴力求解

暴力求解是最直观的方法。不妨按自左向右的次序考查各子串。在初始状态下，$T$的前$m$个字符将与$P$的$m$个字符两两对齐。接下来，自左向右检查相互对齐的这$m$对字符：若当前字符对相互匹配，则转向下一对字符；反之一旦失配，则说明在此位置主串与模式串不可能完全匹配，于是可将$P$串右移一个字符，然后从其首字符开始与$T$中对应的新子串重新对比。若经过检查，当前的$m$对字符均匹配，则意味着整体匹配成功，从而返回匹配子串的位置。

暴力求解代码如下：

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
/*
 * 字符串匹配
 */

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

/*
 * @param: T: 主串
 * @parma: P: 模式串
 * @return: 匹配到返回第一次匹配到的位置，否则返回-1
 */
int stringMatch(string& T, string& P){
    if (T.length() < P.length()) return -1;
    size_t n = T.length(), i = 0;
    size_t m = P.length(), j = 0;
    while (i < n && j < m){
        if (T[i] == P[j]){          // 匹配
            ++i;                    // 转到下一个字符
            ++j;
        } else {
            i = i - j + 1;          // 主串回退
            j = 0;                  // 模式串复位
        }
    }
    if (j != m) return -1;          // 匹配失败
    else return i-j;                // 匹配成功
}

int main(int argc, char** argv){
    string T = "ABCD ABCDEFG";
    string P = "ABCDE";
    cout << stringMatch(T, P) << endl;
    return 1;
}

代码输出：

1
5

当$m<<n$时，上述代码的渐进时间复杂度为$O(nm)$。

2.2. KMP算法

KMP算法详解可参考如下链接：KMP 算法

代码如下：

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
/*
 * 字符串匹配
 */

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

/*
 * @function: 构造模式串的next表
 * @parma: P: 模式串
 * @return: 模式串P的next表
 */
vector<int> buildNext(string& P){
    size_t m = P.length(), j = 0;
    vector<int> next(m);                // next表
    next[0] = -1;
    int t = -1;               // 模式串指针
    while (j < m-1){
        if (t == -1 || P[j] == P[t]){     // 匹配
            ++j;
            ++t;
            next[j] = t;
        } else {                        // 不匹配
            t = next[t];
        }
    }
    return next;
}

/*
 * @function: 字符串匹配，KMP算法
 * @param: T: 主串
 * @parma: P: 模式串
 * @return: 匹配到返回第一次匹配到的位置，否则返回-1
 */
int stringMatch(string& T, string& P){
    if (T.length() < P.length()) return -1;
    vector<int> next = buildNext(P);        // 构造next表
    int n = T.length(), i = 0;
    int m = P.length(), j = 0;
    while (j < m && i < n){                 // 自左向右逐个对比字符
        if (j == -1 || T[i] == P[j]){       // P已移到最左侧或匹配
            ++i;
            ++j;
        } else {
            j = next[j];                    // 模式串右移（主串不用动）
        }
    }
    if (j == m) return i-j;
    else return -1;
}

int main(int argc, char** argv){
    string T = "ABCD ABCDEFG";
    string P = "ABCDEF";
    cout << stringMatch(T, P) << endl;
    return 1;
}

代码输出：

1
5

上述代码的时间复杂度为$O(n+m)$