Box
Box
Posts List
  1. 朴素匹配
  2. KMP算法
    1. Cpp完整代码

KMP Alorithm

朴素匹配

  • 设待匹配串长度为$n$,模版串长度为$m$。
  • 朴素匹配复杂度为$O(m(n - 1))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 暴力字符串匹配算法
def match_str(string_, pattern_):
'''
input:
string_: 待匹配串
pattern_: 模板串
output:
>= 0: 找到,并返回首次匹配位置
< 0: 未找到
'''
for i in range(len(string_) - len(pattern_)):
j = 0
while j < len(pattern_):
if string_[i + j] != pattern_[j]:
break
j += 1
if j == len(pattern_):
return i
return -1

KMP算法

这里就要讲讲部分匹配表,又称为失配函数,作用是让算法无需多次匹配S中的任何字符。

  • 计算部分匹配表

上图中的部分匹配表为:

对应字符 a b a b b
下标 0 1 2 3 4
部分匹配值 0 0 1 2 0

部分匹配值就是”前缀”和”后缀”的最长的共有元素的长度。以ababb为例:

  • a的前缀和后缀都为空集,共有元素的长度为0
  • ab前缀为[a],后缀为[b],共有元素的长度为0
  • aba前缀为[a, ab],后缀为[a, ba],共有元素为[a],长度为1
  • abab前缀为[a, ab, aba],后缀为[b, ab, bab],共有元素为[ab],长度为2
  • ababb前缀为[a, ab, aba, abab],后缀为[b, bb, abb, babb],共有元素的长度为0

“部分匹配”的实质是,有时候,字符串头部和尾部会有重复。当在匹配值出不匹配时,模板串后移的位数 = 已匹配的字符数 - 对应的部分匹配值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 计算模板串的部分匹配表
def pmt(pattern_):
'''
input:
pattern_: 模板串
output:
dfa: 部分匹配表数组
'''
dfa = []
for j in range(len(pattern_)):
max_, tmp = 0, pattern_[:j + 1]
for i in range(len(tmp)):
if tmp[:i] == tmp[len(tmp) - i:] and max_ < i:
max_ = i
dfa.append(max_)
return dfa
  • 全部代码:
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
# kmp算法
def kmp(string_, pattern_):
'''
input:
string_: 待匹配串
pattern_: 模板串
output:
>= 0: 找到,并返回首次匹配位置
< 0: 未找到
'''
# 计算模板串的部分匹配表
def pmt(pattern_):
'''
input:
pattern_: 模板串
output:
dfa: 部分匹配表数组
'''
dfa = []
for j in range(len(pattern_)):
max_, tmp = 0, pattern_[:j + 1]
for i in range(len(tmp)):
if tmp[:i] == tmp[len(tmp) - i:] and max_ < i:
max_ = i
dfa.append(max_)
return dfa

dfa = pmt(pattern_) # 计算部分匹配表
j, i, len_string_, len_pattern_ = 0, 0, len(string_), len(pattern_)
while j < len_string_:
if string_[j] == pattern_[i]:
if i == len_pattern_ - 1:
return j - len_pattern_ + 1
j, i = j + 1, i + 1
elif i > 0: # 状态转移
i = dfa[i - 1]
else:
j += 1
return -1

时间复杂度$O(n)$

Cpp完整代码
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
#include <iostream>
#include <vector>
#include <string>
using namespace std;


// 计算模板串部分匹配表
vector<int> pmt(string pat) {
vector<int> dfa;
for (int j = 0; j < pat.size(); j++) {
int max = 0;
for (int i = 0; i < j + 1; i++) {
vector<string> start, end;
for (int n = 0; n < i; n++) {
string tmp;
tmp = pat[n];
start.push_back(tmp);
tmp = pat[j + 1 - i];
end.push_back(tmp);
}
if (start == end && max < i) {
max = i;
}
}
dfa.push_back(max);
}
return dfa;
}

// kmp 算法
int kmp(string str, string pat) {
vector<int> dfa = pmt(pat); // 计算部分匹配表
int j, i = 0;
int len_str = str.size();
int len_pat = pat.size();
while (j < len_str) {
if (str[j] == pat[i]) {
if (i == len_pat - 1) {
return j - len_pat + 1;
}
j++;
i++;
} else if (i > 0) { // 状态转移
i = dfa[i - 1];
} else {
j++;
}
}
return -1;
}


// 主函数
int main() {
string str = "123234562476qvregerv";
string pat = "76qv";
cout << kmp(str, pat) << endl;
return 0;
}
Supporting
Scan, Support Daidai
  • WeChat scan
  • Alipay scan