去掉注释:#include <iostream>#include <queue>#include <cstring>using namespace std;const int MAXN = 100005; // 最大字符串长度const int MAXM = 26; // 字符集大小struct AC_Automaton { int ch[MAXN][MAXM]; // Trie树 int val[MAXN]; // 节点值 int fail[MAXN]; // 失败指针 int tot; // 节点总数 void init() { memset(ch, 0, sizeof(ch)); memset(val, 0, sizeof(val)); memset(fail, 0, sizeof(fail)); tot = 0; } void insert(string s, int v) { // 插入字符串s,节点值为v int u = 0; for (int i = 0; i < s.size(); i++) { int c = s[i] - 'a'; if (!ch[u][c]) ch[u][c] = ++tot; u = ch[u][c]; } val[u] += v; } void build() { // 构建AC自动机 queue<int> q; for (int i = 0; i < MAXM; i++) { if (ch[0][i]) q.push(ch[0][i]); } while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < MAXM; i++) { if (ch[u][i]) { fail[ch[u][i]] = ch[fail[u]][i]; q.push(ch[u][i]); } else { ch[u][i] = ch[fail[u]][i]; } } val[u] += val[fail[u]]; // 合并节点值 } } int query(string s) { // 查询字符串s中出现的模式串的节点值之和 int u = 0, res = 0; for (int i = 0; i < s.size(); i++) { u = ch[u][s[i] - 'a']; res += val[u]; } return res; }} AC;int main() { AC.init(); int n; cin >> n; for (int i = 1; i <= n; i++) { string s; int v; cin >> s >> v; AC.insert(s, v); } AC.build(); string t; cin >> t; cout << AC.query(t) << endl; return 0;}
时间: 2023-06-26 08:08:13 浏览: 73
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 100005; // 最大字符串长度
const int MAXM = 26; // 字符集大小
struct AC_Automaton {
int ch[MAXN][MAXM]; // Trie树
int val[MAXN]; // 节点值
int fail[MAXN]; // 失败指针
int tot; // 节点总数
void init() {
memset(ch, 0, sizeof(ch));
memset(val, 0, sizeof(val));
memset(fail, 0, sizeof(fail));
tot = 0;
}
void insert(string s, int v) { // 插入字符串s,节点值为v
int u = 0;
for (int i = 0; i < s.size(); i++) {
int c = s[i] - 'a';
if (!ch[u][c]) ch[u][c] = ++tot;
u = ch[u][c];
}
val[u] += v;
}
void build() { // 构建AC自动机
queue<int> q;
for (int i = 0; i < MAXM; i++) {
if (ch[0][i]) q.push(ch[0][i]);
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < MAXM; i++) {
if (ch[u][i]) {
fail[ch[u][i]] = ch[fail[u]][i];
q.push(ch[u][i]);
} else {
ch[u][i] = ch[fail[u]][i];
}
}
val[u] += val[fail[u]]; // 合并节点值
}
}
int query(string s) { // 查询字符串s中出现的模式串的节点值之和
int u = 0, res = 0;
for (int i = 0; i < s.size(); i++) {
u = ch[u][s[i] - 'a'];
res += val[u];
}
return res;
}
} AC;
int main() {
AC.init();
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
string s;
int v;
cin >> s >> v;
AC.insert(s, v);
}
AC.build();
string t;
cin >> t;
cout << AC.query(t) << endl;
return 0;
}
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![text/plain](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)