bzoj1195 [HNOI2006]最短母串 AC 自动机+状压+bfs
2024-10-07 08:36:05
题目传送门
https://lydsy.com/JudgeOnline/problem.php?id=1195
题解
建立 AC 自动机,然后构建出 trie 图。
然后直接在 trie 图上走。但是我们需要经过每一个串。
所以我们处理一下每个点代表了哪些串,然后把状态加入进 bfs 状态。
然后 bfs 就可以了。
\(O(n)\)。
#include<bits/stdc++.h>
#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back
template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}
template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}
typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;
template<typename I> inline void read(I &x) {
int f = 0, c;
while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
x = c & 15;
while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
f ? x = -x : 0;
}
const int N = 12 + 1;
const int M = 50 + 1;
const int NM = 12 * 50 + 1;
const int NP = (1 << 12);
const int NMP = 12 * 50 * ((1 << 12) - 1) + 1;
int n, m, nod;
int q[NMP], q2[NMP], fr[NM][NP];
char s[N], ans[NM];
struct Node { int c[26], fa, v; char s; } t[NM];
inline void ins(char *s, int id) {
int n = strlen(s + 1), o = 0;
for (int i = 1; i <= n; ++i) {
if (!t[o].c[s[i] - 'A']) t[o].c[s[i] - 'A'] = ++nod, t[nod].s = s[i];
o = t[o].c[s[i] - 'A'];
}
t[o].v |= 1 << (id - 1);
}
inline void build() {
int hd = 0, tl = 0;
for (int i = 0; i < 26; ++i) if (t[0].c[i]) q[++tl] = t[0].c[i];
while (hd < tl) {
int x = q[++hd]; t[x].v |= t[t[x].fa].v;
for (int i = 0; i < 26; ++i)
if (t[x].c[i]) t[t[x].c[i]].fa = t[t[x].fa].c[i], q[++tl] = t[x].c[i];
else t[x].c[i] = t[t[x].fa].c[i];
}
}
inline void work() {
int hd = 0, tl = 1, S = (1 << n) - 1;
q[tl] = 0, q2[tl] = 0, fr[0][0] = -1;
while (hd < tl) {
int x = q[++hd];
int s = q2[hd];
// dbg("x = %d, s = %d\n", x, s);
for (int i = 0; i < 26; ++i) if (t[x].c[i]) {
int y = t[x].c[i], ss = s | t[y].v;
// dbg("y = %d, ss = %d\n", y, ss);
if (!fr[y][ss]) {
fr[y][ss] = hd, q[++tl] = y, q2[tl] = ss;
// dbg("****** y = %d, ss = %d\n", y, ss);
if (ss == S) {
int len = 0, z = y, zs = ss, zz;
while (~fr[z][zs]) ans[++len] = t[z].s, zz = fr[z][zs], z = q[zz], zs = q2[zz];
while (len) putchar(ans[len--]);
puts("");
// dbg("*********\n");
return;
}
assert(fr[y][ss]);
}
}
}
}
inline void init() {
read(n);
for (int i = 1; i <= n; ++i) scanf("%s", s + 1), ins(s, i);
build();
// dbg("*************\n");
}
int main() {
#ifdef hzhkk
freopen("hkk.in", "r", stdin);
#endif
init();
work();
fclose(stdin), fclose(stdout);
return 0;
}
最新文章
- 【RabbitMQ】Publish/Subscribe
- 初学AOP
- C语言解析json类型数据
- ";this class is not key value coding-compliant for the key ...";问题的解决
- 读取计算机的OEM信息
- 获取json对象的id或者根据name获取id
- C语言结构体的强制类型转换
- Delphi下的RTTI函数大全
- Spring MVC PageNotFound.noHandlerFound No mapping found for HTTP request with URI
- 安装dotnet core
- Asynchronous vs synchronous client applications(MQTT)
- 团队作业4——第一次项目冲刺(Alpha版本)2017.11.19
- 每天记录一点:NetCore获得配置文件 appsettings.json
- [转帖]流程控制:for 循环
- 转载---滋滋有味看完的一篇文章关于python与java夜话
- Linux磁盘空间满了的排查与解决思路
- 从0开始搭建vue+webpack脚手架(四)
- CodeFirst Update-Database 出现对象&#39;DF__**__**__**&#39; 依赖于 列&#39;**&#39;。
- 设置(更改)Mysql 自增ID的起始值
- Vim global命令和重复操作
热门文章
- java 解析上传的Excel文件
- A 内存挂 B 封包挂 C 钩子挂 D CALL挂 外挂
- 开发-日常工具:TFS(Team Foundation Server)
- 【Python】—— 获取当前运行函数名称和类方法名称
- Delphi XE2 之 FireMonkey 入门(40) - 控件基础: TMemo
- ActionList及Action使用
- 快速编写 <;a>; ————CSS3
- jmeter遍历时间戳
- ionic3遇到的刷新页面服务器关闭的问题
- Github 上 Star 最多的个人 Spring Boot 开源学习项目(三)