题目传送门: 我是传送门
实现一个简单的正则匹配, 支持克林* 和.任意字符
用 NFA，没有用 epsilon 边。
build_nfa 返回的是包含全部状态的一个 vector，然后 states[0] 是初始态，可以再加一个终止态，不过我实现的时候偷懒了，然后就是模拟 NFA
C++ 实现
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
| struct nfa_state {
char c;
bool any;
bool accepted;
vector<int> next;
nfa_state(char c) : next() {
accepted = false;
any = false;
this->c = c;
}
};
vector<nfa_state> build_nfa(const char *s) {
vector<nfa_state> states;
states.push_back(nfa_state(0));
vector<int> prevs = {0};
for (size_t i = 0; s[i]; i++) {
states.push_back(nfa_state(s[i]));
auto id = (int)states.size() - 1;
auto& st = states[id];
if (s[i + 1] == '*') {
st.any = true;
i++;
}
for (auto pi : prevs) {
states[pi].next.push_back(id);
}
if (st.any) {
st.next.push_back(id);
} else {
prevs.clear();
}
prevs.push_back(id);
}
for (auto pi : prevs) {
states[pi].accepted = true;
}
return states;
}
bool nfa_match(vector<nfa_state> &states, string &s) {
unordered_set<int> next;
unordered_set<int> cur;
auto accepted = states[0].accepted;
for (auto i : states[0].next) {
cur.insert(i);
if (!accepted) {
accepted = states[i].any && states[i].accepted;
}
}
auto p = 0;
while (!cur.empty() && p != s.length()) {
next.clear();
accepted = false;
for (auto it = cur.begin(); it != cur.end(); it++) {
auto &st = states[*it];
if (st.c == '.' || st.c == s[p]) {
if (!accepted) {
accepted = st.accepted;
}
for (auto i : st.next) {
next.insert(i);
}
}
}
p++;
swap(cur, next);
}
return accepted && p == s.length();
}
|