6 条题解
-
3
P3808 【模板】AC 自动机（简单版）
#include <bits/stdc++.h> using namespace std; const int MAXN = 1123456; int n; struct AC { int tr[MAXN][26], tot; //根节点为 0 int cnt[MAXN], fail[MAXN]; void insert(string &s) { int u = 0; // cout << u; for (int i = 0; i < s.length(); i++) { // cout << " -> " << s[i]; if (!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++tot; u = tr[u][s[i] - 'a']; } cnt[u]++; // cout << " cnt:" << cnt[u] << endl; } queue<int> q; void build() { for (int i = 0; i < 26; i++) if (tr[0][i]) q.push(tr[0][i]); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < 26; i++) { if (tr[u][i]) { fail[tr[u][i]] = tr[fail[u]][i]; q.push(tr[u][i]); } else tr[u][i] = tr[fail[u]][i]; } } } int query(string &s) { int res = 0; int u = 0; for (int i = 0; i < s.length(); i++) { u = tr[u][s[i] - 'a']; for (int j = u; j != 0 && cnt[j] != -1; j = fail[j]) { res += cnt[j]; cnt[j] = -1; } } return res; } }; AC ac; string s; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> s; ac.insert(s); } ac.build(); cin >> s; cout << ac.query(s) << endl; return 0; } -
2
33DAI LV 6 (1/1) @ 2023-6-13 15:15:32
P2292 [HNOI2004] L 语言
#include<bits/stdc++.h> using namespace std; const int MAXN = 1123456; struct AC { int tr[MAXN][26], tot; //根节点为 0 int cnt[MAXN], fail[MAXN],len[MAXN]; void insert(string &s) { int u = 0; // cout << u; for (int i = 0; i < s.length(); i++) { // cout << " -> " << s[i]; if (!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++tot; u = tr[u][s[i] - 'a']; } cnt[u]++; len[u]=s.length(); // cout << " cnt:" << cnt[u] << endl; } queue<int> q; //当前点有哪些20以内长度的后缀存在 int g[MAXN]; void build() { for (int i = 0; i < 26; i++) if (tr[0][i]) q.push(tr[0][i]); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < 26; i++) { if (tr[u][i]) { fail[tr[u][i]] = tr[fail[u]][i]; q.push(tr[u][i]); } else tr[u][i] = tr[fail[u]][i]; } } for(int u=1; u<=tot; u++) { g[u]=0; for (int i = u; i!=0; i = fail[i]) if (cnt[i] && len[i] <= 20) g[u] |= (1 << (len[i] - 1)); } } bool f[2123456]; int query(string &s) { int res = 0; int x = 0; //前 20 位的 f 的状压 int u = 0; f[0] = true; for (int i = 1; i <= s.length(); i++) { u = tr[u][s[i-1] - 'a']; x = ((1 << 20) - 1) & ((x << 1) | f[i - 1]); f[i] = (x & g[u]) != 0; if(f[i]) res=max(res,i); } return res; } }; AC ac; int n,m; string s,t; int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m; for(int i=1; i<=n; i++) { cin>>s; ac.insert(s); } ac.build(); for(int i=1; i<=m; i++) { cin>>t; cout<<ac.query(t)<<"\n"; } return 0; } -
0
P4045 [JSOI2009] 密码
#include <bits/stdc++.h> using namespace std; const int MAXN = 10; int L, n; struct AC { int tr[MAXN * 10 + 5][26], tot; //根节点为 0 int fail[MAXN * 10 + 5]; int ids[MAXN * 10 + 5]; void insert(string &s, int id) { int u = 0; for (int i = 0; i < s.length(); i++) { if (!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++tot; u = tr[u][s[i] - 'a']; } ids[u] |= (1 << id); } queue<int> q; void build() { for (int i = 0; i < 26; i++) if (tr[0][i]) q.push(tr[0][i]); while (!q.empty()) { int u = q.front(); q.pop(); ids[u] |= ids[fail[u]]; for (int i = 0; i < 26; i++) { if (tr[u][i]) { fail[tr[u][i]] = tr[fail[u]][i]; q.push(tr[u][i]); ids[tr[u][i]] |= ids[fail[tr[u][i]]]; } else tr[u][i] = tr[fail[u]][i]; } } } } ac; string s[30]; //第i位，匹配到了ac上第j个节点，完成了k这些字符串的方案数 long long f[30][105][(1 << 10) - 1 + 10]; // out // 寄搜，每个状态能否走到终点。0：没搜过、1：能走到、-1：不能走到 int flag[30][105][(1 << 10) - 1 + 10]; int dfsCheck(int i, int j, int k) { if (flag[i][j][k]) return flag[i][j][k]; if (i == L) { if (k == (1 << n) - 1) return flag[i][j][k] = 1; else return flag[i][j][k] = -1; } flag[i][j][k] = -1; for (int ch = 0; ch < 26; ch++) { int x = ac.tr[j][ch]; int y = k | ac.ids[x]; int res = dfsCheck(i + 1, x, y); if (res == 1) flag[i][j][k] = 1; } return flag[i][j][k]; } char ans[30]; void dfsOut(int i, int j, int k) { if (flag[i][j][k] != 1) return; if (i == L) { for (int i = 0; i < L; i++) cout << ans[i]; cout << "\n"; return; } for (int ch = 0; ch < 26; ch++) { int x = ac.tr[j][ch]; int y = k | ac.ids[x]; ans[i] = 'a' + ch; dfsOut(i + 1, x, y); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> L >> n; for (int i = 0; i < n; i++) { cin >> s[i]; ac.insert(s[i], i); } ac.build(); // dp f[0][0][0] = 1; for (int i = 0; i < L; i++) for (int j = 0; j <= ac.tot; j++) for (int k = 0; k <= (1 << n) - 1; k++) { // f[i][j][k] -> f[i+1][x][y] if (f[i][j][k]) for (int ch = 0; ch < 26; ch++) { int x = ac.tr[j][ch]; //下一个字符选 ch 对应的下一个节点 int y = k | ac.ids[x]; //下一个节点包括当前节点经过了哪些单词 f[i + 1][x][y] += f[i][j][k]; } } long long ans = 0; for (int i = 0; i <= ac.tot; i++) ans += f[L][i][(1 << n) - 1]; // out if (ans > 42) cout << ans << "\n"; else { cout << ans << "\n"; dfsCheck(0, 0, 0); dfsOut(0, 0, 0); } return 0; } -
0
P2414 [NOI2011] 阿狸的打字机
#include<bits/stdc++.h> using namespace std; const int MAXN = 112345; struct AC { int tr[MAXN][26], tot;//根节点为 0 int idx[MAXN],idTot;//第i个字符串对应的位置 int fa[MAXN], fail[MAXN]; vector<int> FT[MAXN];//fail tree int dfn[MAXN],dfnn[MAXN],dfId;//dfs序(in,out) void dfs(int u) { dfn[u]=++dfId; for(int i=0; i<FT[u].size(); i++) { int v=FT[u][i]; dfs(v); } dfnn[u]=dfId; } void insert(string &s) { int u = 0; for (int i = 0; i < s.length(); i++) { if('a'<=s[i]&&s[i]<='z') { if (!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++tot; int nxt=tr[u][s[i] - 'a']; fa[nxt]=u; u = nxt; } else if(s[i]=='P') { idx[++idTot] = u; } else if(s[i]=='B') { u=fa[u]; } } } queue<int> q; void build() { for (int i = 0; i < 26; i++) if (tr[0][i]) q.push(tr[0][i]); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < 26; i++) { if (tr[u][i]) { fail[tr[u][i]] = tr[fail[u]][i]; q.push(tr[u][i]); } else tr[u][i] = tr[fail[u]][i]; } } //build fail tree for(int i=1; i<=tot; i++){ FT[fail[i]].push_back(i); } dfs(0); } }; AC ac; string s; int n,m; //离线询问 vector<pair<int,int> > qa[112345]; int ans[112345]; //树状数组 int ta[MAXN]; int lowbit(int x) { return x&(-x); } void add(int x,int y) { for(int i=x; i<=n; i+=lowbit(i)) ta[i]+=y; } int sum(int x) { int res=0; for(int i=x; i>=1; i-=lowbit(i)) res+=ta[i]; return res; } int main() { //ios::sync_with_stdio(false); //cin.tie(0); cin>>s; n=s.length(); ac.insert(s); ac.build(); cin>>m; for(int i=1; i<=m; i++) { int xx,yy; cin>>xx>>yy; qa[yy].push_back(make_pair(xx,i)); } int u=0; int nowQ=0; for(int i=0; i<s.length(); i++) { if('a'<=s[i]&&s[i]<='z') { u=ac.tr[u][s[i]-'a']; add(ac.dfn[u],1); } else if(s[i]=='B') { add(ac.dfn[u],-1); u=ac.fa[u]; } else if(s[i]=='P') { nowQ++; for(int j=0; j<qa[nowQ].size(); j++) { int x=qa[nowQ][j].first; int id=qa[nowQ][j].second; ans[id]=sum(ac.dfnn[ac.idx[x]])-sum(ac.dfn[ac.idx[x]]-1); } } } for(int i=1; i<=m; i++) cout<<ans[i]<<"\n"; return 0; } -
0
P5357 【模板】AC 自动机（二次加强版）
#include <bits/stdc++.h> using namespace std; const int MAXN = 212345; int n; struct AC { int tr[MAXN][26], tot; // 根节点为 0 int cnt[MAXN], fail[MAXN]; int idx[MAXN]; // 每个模式串对应的终点坐标 // fail树相关 int inD[MAXN]; void insert(string &s, int id) { int u = 0; // cout << u; for (int i = 0; i < s.length(); i++) { // cout << " -> " << s[i]; if (!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++tot; u = tr[u][s[i] - 'a']; } idx[id] = u; // cnt[u]++; // cout << " cnt:" << cnt[u] << endl; } queue<int> q; void build() { for (int i = 0; i < 26; i++) if (tr[0][i]) q.push(tr[0][i]); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < 26; i++) { if (tr[u][i]) { fail[tr[u][i]] = tr[fail[u]][i]; inD[tr[fail[u]][i]]++; q.push(tr[u][i]); } else tr[u][i] = tr[fail[u]][i]; } } } bool vis[MAXN]; void query(string &s) { int u = 0; for (int i = 0; i < s.length(); i++) { u = tr[u][s[i] - 'a']; cnt[u]++; } queue<int> q; for (int i = 0; i <= tot; i++) if (inD[i] == 0) q.push(i), vis[i] = true; while (!q.empty()) { int now = q.front(); q.pop(); int nxt = fail[now]; inD[nxt]--; cnt[nxt] += cnt[now]; if (inD[nxt] == 0 && !vis[nxt]) q.push(nxt), vis[nxt] = true; } } }; AC ac; string s; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> s; ac.insert(s, i); } ac.build(); cin >> s; ac.query(s); /* for (int i = 0; i <= ac.tot; i++) { cout << i << ": "; for (int j = 0; j <= 1; j++) cout << ac.tr[i][j] << " "; cout << ", " << ac.fail[i] << "\n"; } */ for (int i = 1; i <= n; i++) cout << ac.cnt[ac.idx[i]] << "\n"; //<< " " << ac.idx[i] return 0; } -
0
P3796 【模板】AC 自动机（加强版）
#include <bits/stdc++.h> using namespace std; const int MAXT = 50 + 5; const int MAXN = 150 + 5; int T, n; string s[MAXT][MAXN], t; int scnt[MAXT][MAXN]; struct AC { int tr[MAXN * 70 + 5][26], tot; //根节点为 0 int cnt[MAXN * 70 + 5], fail[MAXN * 70 + 5], idx[MAXN * 70 + 5]; void insert(string &s, int id) { int u = 0; // cout << u; for (int i = 0; i < s.length(); i++) { // cout << " -> " << s[i]; if (!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++tot; u = tr[u][s[i] - 'a']; } idx[u] = id; // cout << " cnt:" << cnt[u] << endl; } queue<int> q; void build() { for (int i = 0; i < 26; i++) if (tr[0][i]) q.push(tr[0][i]); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < 26; i++) { if (tr[u][i]) { fail[tr[u][i]] = tr[fail[u]][i]; q.push(tr[u][i]); } else tr[u][i] = tr[fail[u]][i]; } } } int query(string &s) { int res = 0; int u = 0; for (int i = 0; i < s.length(); i++) { u = tr[u][s[i] - 'a']; for (int j = u; j != 0 && cnt[j] != -1; j = fail[j]) cnt[j]++; } for (int i = 0; i <= tot; i++) if (idx[i]) res = max(res, cnt[i]), scnt[T][idx[i]] = cnt[i]; return res; } }; AC ac[MAXT]; int main() { ios::sync_with_stdio(false); cin.tie(0); while (cin >> n) { if (n == 0) break; T++; for (int i = 1; i <= n; i++) { cin >> s[T][i]; ac[T].insert(s[T][i], i); } ac[T].build(); cin >> t; int ans = ac[T].query(t); cout << ans << "\n"; for (int i = 1; i <= n; i++) if (scnt[T][i] == ans) cout << s[T][i] << "\n"; } return 0; }
- 1