【C++】字符串|匹配类问题模板
这一篇文章主要涉及到在一个主字符串中匹配是否出现某个/某几个需要寻找的字符串等问题的算法。
字典树 (Trie)
字典树是一种很常用的树形数据结构。相当于将字符串压缩存储。
字典树的应用还是非常广泛的，除了基础的压缩存储字符串外还能用于异或操作和AC 自动机。
基本模板
题目：P2580 于是他错误的点名开始了（https://www.luogu.com.cn/problem/P2580）
代码默认为存26个小写字母，如果要存更多字符修改vector第二维大小和j的处理即可。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
vector<vector<int>> trie;
vector<int> cnt;
int pid = 0;
void insert(string& s)
{
int pos = 0;
for (auto& i : s)
{
int j = i - 'a';
if (!trie[pos][j])
{
trie[pos][j] = ++pid;
trie.emplace_back(vector<int>(26));
cnt.emplace_back(0);
}
pos = trie[pos][j];
}
cnt[pos]++;
}
int query(string& s)
{
int pos = 0;
for (auto& i : s)
{
int j = i - 'a';
if (!trie[pos][j]) return 0;
pos = trie[pos][j];
}
int res = cnt[pos]++;
return res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
string tmp;
trie.emplace_back(vector<int>(26));
cnt.emplace_back(0);
cin >> n;
while (n--)
{
cin >> tmp;
insert(tmp);
}
cin >> m;
while (m--)
{
cin >> tmp;
int q = query(tmp);
if (q == 1) cout << "OK" << endl;
else if (q > 1) cout << "REPEAT" << endl;
else cout << "WRONG" << endl;
}
return 0;
}
01-trie
将数的二进制表示看做一个字符串，就可以建出字符集为 {0,1} 的 trie 树。
题目：P10471 最大异或对 The XOR Largest Pair（https://www.luogu.com.cn/problem/P10471）
使用贪心思想：想要异或大，就按位尽量取不同的数字。
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;
vector<vector<int>> trie;
int pid = 0;
void insert(int n)
{
bitset<31> bs(n);
int pos = 0;
for (int i = 30; i >= 0; i--)
{
if (!trie[pos][bs[i]])
{
trie[pos][bs[i]] = ++pid;
trie.emplace_back(vector<int>(2));
}
pos = trie[pos][bs[i]];
}
}
int query(int n)
{
bitset<31> bs(n), res;
int pos = 0;
for (int i = 30; i >= 0; i--)
{
if (trie[pos][!bs[i]])
{
res[i] = 1;
pos = trie[pos][!bs[i]];
}
else pos = trie[pos][bs[i]];
}
return res.to_ulong();
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
trie.emplace_back(vector<int>(2));
int n, ans = 0;
cin >> n;
vector<int> arr(n);
for (auto& i : arr) cin >> i;
for (auto& i : arr) insert(i);
for (auto& i : arr) ans = max(ans, query(i));
cout << ans << endl;
return 0;
}KMP 算法
该算法由 Knuth、Pratt 和 Morris 在 1977 年共同发布，是一种可以在 O(n) 的时间内查找某一个字符串（模式串）在主串内所有出现位置的贪心算法。
目前网上主要流行着3~4类实现，由于博主学了luogu/oi-wiki上的版本然后被数据结构老师用其他版本狠狠拷打了一次，所以决定把所有版本都记录一下。
首先来大致说明一下各版本之间的区别：其实仅仅是next数组的定义上不太一样。
在原论文/数据结构(严蔚敏)版中：next[j]指的是前j-1位的最长的相等的真前缀与真后缀的长度。而这两者均采用了1作为字符串起始下标（因此产生了同学以0为起始下标的版本）
在luogu/oi-wiki版中：next[j]指的是前j位的最长的相等的真前缀与真后缀的长度。
同时，也存在着在此基础上继续优化重合部分的nextval版本（其实原论文中就将此称为next数组，但是为了方便理解我们按照数据结构教材来）
如果上面的解释成功让你一头雾水了的话，我们直接举个例子：
| 字符串 | a | b | a | b | a | b | c | a | a |
| 下标(1-based) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| next[j](原论文版) | 0 | 1 | 1 | 2 | 3 | 4 | 5 | 1 | 2 |
| next[j](竞赛版) | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | 1 |
| next[j](同学版) | -1 | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
可以看出，在同学版的基础上每一位加1就可以得到教材中的版本（其实就是从0-based升一位到1-based）。而luogu/oi-wiki的版本右移一位就是同学的版本（因为竞赛版算第j位时考虑1~j，领先同学版的算j位考虑1~j-1一位）
那么基于next数组可以进一步求出nextval数组。即当next跳回后如果字符仍相同，可以继续跳的情况下，直接一步跳到next多次跳到的最终位置。
| 字符串 | a | b | a | b | a | b | c | a | a |
| 下标(1-based) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| next[j](原论文版) | 0 | 1 | 1 | 2 | 3 | 4 | 5 | 1 | 2 |
| nextval[j] | 0 | 1 | 0 | 1 | 0 | 1 | 5 | 0 | 2 |
题目：P3375 【模板】KMP（https://www.luogu.com.cn/problem/P3375）
注意：luogu中KMP模板题目采用的是和oi-wiki一致的next[j]定义，即1~j
OI-WIKI版
// KMP oi-wiki 版
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
string s1, s2;
cin >> s1 >> s2;
s1.insert(s1.begin(), '#');
s2.insert(s2.begin(), '#');
vector<int> next(s2.size());
for (int i = 2, j = 0; i < s2.size(); i++)
{
while (j && s2[i] != s2[j + 1]) j = next[j];
if (s2[i] == s2[j + 1]) j++;
next[i] = j;
}
for (int i = 1, j = 0; i < s1.size(); i++)
{
while (j && s1[i] != s2[j + 1]) j = next[j];
if (s1[i] == s2[j + 1]) j++;
if (j == s2.size() - 1)
{
cout << i - j + 1 << endl;
j = next[j];
}
}
for (int i = 1; i < s2.size(); i++)
{
cout << next[i] << " ";
}
cout << endl;
return 0;
}其中18-23行与以下写法等效：
int i = 2, j = 0;
while (i < s2.size())
{
if (!j || s2[i] == s2[j + 1])
{
if (s2[i] == s2[j + 1]) j++;
next[i] = j;
i++;
}
else j = next[j];
}原论文/教材基础版
// KMP 教材版
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
string s1, s2;
cin >> s1 >> s2;
s1.insert(s1.begin(), '$');
s2.insert(s2.begin(), '$');
vector<int> next(s2.size());
int i = 1, j = 0;
while (i < s2.size())
{
if (!j || s2[i] == s2[j])
{
i++, j++;
next[i] = j;
}
else j = next[j];
}
i = 1, j = 1;
while (i < s1.size() && j < s2.size())
{
if (!j || s1[i] == s2[j]) i++, j++;
else j = next[j];
if (j > s2.size() - 1)
{
cout << i - j + 1 << endl;
j = next[j];
}
}
return 0;
}原论文/教材升级版
即基于nextval的版本，nextval是通过当前位前面的next求出的，因此可以通过修改next计算过程直接求出。
// KMP 教材版
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
string s1, s2;
cin >> s1 >> s2;
s1.insert(s1.begin(), '$');
s2.insert(s2.begin(), '$');
vector<int> nextval(s2.size());
int i = 1, j = 0;
while (i < s2.size())
{
if (!j || s2[i] == s2[j])
{
i++, j++;
if (s2[i] != s2[j]) nextval[i] = j;
else nextval[i] = nextval[j];
}
else j = nextval[j];
}
i = 1, j = 1;
while (i < s1.size() && j < s2.size())
{
if (!j || s1[i] == s2[j]) i++, j++;
else j = nextval[j];
if (j > s2.size() - 1)
{
cout << i - j + 1 << endl;
j = nextval[j];
}
}
return 0;
}Z 函数 (扩展 KMP)
Z 函数定义：对于一个长度为 n 的字符串 s，定义函数 z[i] 表示 s 和 s[i,n]（即以 s[i] 开头的后缀）的最长公共前缀（LCP）的长度。
规定 z[1]=n (字符串本身的长度)。
| 字符串 | a | b | a | c | a | b | a |
| 下标(1-based) | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| z[i] | 7 | 0 | 1 | 0 | 3 | 0 | 1 |
存在一种线性计算的方法，使用一种盒子（Z-box）加速计算。
题目：P5410 【模板】扩展 KMP/exKMP（Z 函数）（https://www.luogu.com.cn/problem/P5410）
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
using ll = long long;
ll calc(vector<int>& arr)
{
ll res = 0;
for (ll i = 1; i < arr.size(); i++)
{
res ^= (i * (arr[i] + 1));
}
return res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
string sa, sb;
cin >> sa >> sb;
int n = sa.size(), m = sb.size();
sa.insert(sa.begin(), '%');
sb.insert(sb.begin(), '%');
vector<int> z(sb.size()), p(sa.size());
z[1] = sb.size() - 1;
for (int i = 2, l = 0, r = 0; i <= m; i++)
{
if (i <= r) z[i] = min(z[i - l + 1], r - i + 1);
while (i + z[i] <= m && sb[1 + z[i]] == sb[i + z[i]]) z[i]++;
if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
}
cout << calc(z) << endl;
for (int i = 1, l = 0, r = 0; i <= n; i++)
{
if (i <= r) p[i] = min(z[i - l + 1], r - i + 1);
while (1 + p[i] <= m && i + p[i] <= n && sb[1 + p[i]] == sa[i + p[i]]) p[i]++;
if (i + p[i] - 1 > r) l = i, r = i + p[i] - 1;
}
cout << calc(p) << endl;
return 0;
}AC 自动机
介绍：AC 自动机是以 Trie 的结构为基础，结合 KMP 的思想建立的自动机，可用于解决查找多个字符串（模式串）在主串内的所有出现位置等任务。
ps:AC在这里是人名（Aho–Corasick）的缩写，不是Accepted的缩写。。很可惜：使用AC自动机并不能自动AC。
AC 自动机可以利用fail回跳指针一次求出当前匹配位置的所有匹配模式串（利用后缀）。并利用转移边处理只匹配了一部分的问题（防止从头匹配）。
基本模板
题目：P3808 AC 自动机（简单版）（https://www.luogu.com.cn/problem/P3808）
代码默认只统计模式串的首次出现，如需统计全部出现只需去掉重置cnt[j]即可。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
vector<vector<int>> trie;
vector<int> cnt, fail;
int pid = 0;
void insert(string& s)
{
int pos = 0;
for (auto& i : s)
{
int j = i - 'a';
if (!trie[pos][j])
{
trie[pos][j] = ++pid;
trie.emplace_back(vector<int>(26));
cnt.emplace_back(0);
}
pos = trie[pos][j];
}
cnt[pos]++;
}
void build()
{
fail.resize(cnt.size());
queue<int> q;
for (int i = 0; i < 26; i++)
{
if (trie[0][i]) q.emplace(trie[0][i]);
}
while (!q.empty())
{
auto u = q.front();
q.pop();
for (int i = 0; i < 26; i++)
{
int v = trie[u][i];
if (v)
{
fail[v] = trie[fail[u]][i];
q.emplace(v);
}
else trie[u][i] = trie[fail[u]][i];
}
}
}
int query(string& s)
{
int pos = 0, ans = 0;
for (auto& i : s)
{
pos = trie[pos][i - 'a'];
for (int j = pos; j && cnt[j] != -1; j = fail[j])
{
ans += cnt[j];
cnt[j] = -1;
}
}
return ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
string tmp;
trie.emplace_back(vector<int>(26));
cnt.emplace_back(0);
cin >> n;
while (n--)
{
cin >> tmp;
insert(tmp);
}
build();
cin >> tmp;
cout << query(tmp) << endl;
return 0;
}效率优化
虽然 AC 自动机已经很快，但是每次匹配一直向 fail 边跳来找到所有的匹配，仍然可能超时。
观察到时间主要浪费在查询时每次都要跳 fail。如果我们可以预先记录，最后一并求和，那么效率就会优化。
于是我们按照 fail 树，做一次内向树上的拓扑排序，就能一次性求出所有模式串的出现次数。
题目：P5357 【模板】AC 自动机（https://www.luogu.com.cn/problem/P5357）
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
vector<int> ans;
int pid = 0, cid = 0;
struct node
{
vector<int> ch = vector<int>(26);
int fail = 0;
int in = 0;
int sid = 0;
int cnt = 0;
};
vector<node> trie;
int insert(string& s)
{
int pos = 0;
for (auto& i : s)
{
int j = i - 'a';
if (!trie[pos].ch[j])
{
trie[pos].ch[j] = ++pid;
trie.emplace_back();
}
pos = trie[pos].ch[j];
}
if (!trie[pos].sid)
{
trie[pos].sid = ++cid;
ans.emplace_back(0);
}
return trie[pos].sid;
}
void build()
{
queue<int> q;
for (int i = 0; i < 26; i++)
{
if (trie[0].ch[i]) q.emplace(trie[0].ch[i]);
}
while (!q.empty())
{
auto u = q.front();
q.pop();
for (int i = 0; i < 26; i++)
{
int v = trie[u].ch[i];
if (v)
{
trie[v].fail = trie[trie[u].fail].ch[i];
trie[trie[v].fail].in++;
q.emplace(v);
}
else trie[u].ch[i] = trie[trie[u].fail].ch[i];
}
}
}
void query(string& s)
{
int pos = 0;
for (auto& i : s)
{
pos = trie[pos].ch[i - 'a'];
trie[pos].cnt++;
}
}
void topusort()
{
queue<int> q;
for (int i = 1; i <= pid; i++)
{
if (trie[i].in == 0) q.emplace(i);
}
while (!q.empty())
{
auto u = q.front();
q.pop();
ans[trie[u].sid] = trie[u].cnt;
int v = trie[u].fail;
trie[v].cnt += trie[u].cnt;
trie[v].in--;
if (trie[v].in == 0) q.emplace(v);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
string tmp;
ans.emplace_back(0);
trie.emplace_back();
cin >> n;
vector<int> order(n);
for (auto& i : order)
{
cin >> tmp;
i = insert(tmp);
}
build();
cin >> tmp;
query(tmp);
topusort();
for (auto& i : order)
{
cout << ans[i] << endl;
}
return 0;
}目前有关字符串的匹配相关问题就这些内容。希望我以后遗忘可以慢一点。。。同时如果这也能帮到你，我很荣幸。真的。。
版权声明：
作者：Toms Project
链接：https://blog.projectoms.com/pages/1683.html
来源：Toms Project 官方博客
文章版权归作者所有，未经允许请勿转载。
共有 0 条评论