【bzoj1195】[HNOI2006]最短母串 AC自动机+状态压缩+BFS最短路
状态 压缩 BFS 短路 AC 最短 自动机
2023-09-11 14:22:40 时间
原文地址:http://www.cnblogs.com/GXZlegend/p/6825226.html
题目描述
给定n个字符串(S1,S2,„,Sn),要求找到一个最短的字符串T,使得这n个字符串(S1,S2,„,Sn)都是T的子串。
输入
第一行是一个正整数n(n<=12),表示给定的字符串的个数。以下的n行,每行有一个全由大写字母组成的字符串。每个字符串的长度不超过50.
输出
只有一行,为找到的最短的字符串T。在保证最短的前提下,如果有多个字符串都满足要求,那么必须输出按字典序排列的第一个。
样例输入
2
ABCD
BCDABC
样例输出
ABCDABC
题解
AC自动机+BFS
先求出fail数组和Trie图,同时标记每个位置是哪些字符串的结尾,用二进制储存。
要求包含所有串的最小长度,需要记录当前包含哪些串,需要状压。
当到达字符串结尾时,更改状态。
所以Trie图可以看成一个分层图,所求为0,1到(1<<n)-1,i的最短路。
由于每条路径代表一个字符,所以边权为1,可以使用BFS求最短路得解。
#include <cstdio> #include <cstring> char str[60] , ch[610] , ans[610]; int tot = 1 , next[610][26] , fail[610] , val[610] , qx[1500010] , qy[1500010] , l , r , dis[610][4096] , fromp[610][4096]; void build() { int x , i; for(i = 0 ; i < 26 ; i ++ ) next[0][i] = 1; l = r = 1 , qx[1] = 1; while(l <= r) { x = qx[l ++ ]; for(i = 0 ; i < 26 ; i ++ ) { if(next[x][i]) fail[next[x][i]] = next[fail[x]][i] , val[next[x][i]] |= val[fail[next[x][i]]] , qx[++r] = next[x][i]; else next[x][i] = next[fail[x]][i]; } } } int main() { int n , l , i , j , x , y; scanf("%d" , &n); for(i = 1 ; i <= n ; i ++ ) { scanf("%s" , str + 1) , l = strlen(str + 1) , x = 1; for(j = 1 ; j <= l ; j ++ ) { if(!next[x][str[j] - 'A']) next[x][str[j] - 'A'] = ++tot; x = next[x][str[j] - 'A'] , ch[x] = str[j]; } val[x] |= 1 << (i - 1); } build(); memset(dis , -1 , sizeof(dis)); l = r = 1 , qx[1] = 1 , qy[1] = 0 , dis[1][0] = 0; while(l <= r) { x = qx[l] , y = qy[l]; for(i = 0 ; i < 26 ; i ++ ) { int tx = next[x][i] , ty = y | val[tx]; if(dis[tx][ty] == -1) { dis[tx][ty] = dis[x][y] + 1 , fromp[tx][ty] = l; if(ty == (1 << n) - 1) { int px = tx , py = ty , tmp; for(i = dis[tx][ty] ; i ; i -- ) ans[i] = ch[px] , tmp = fromp[px][py] , px = qx[tmp] , py = qy[tmp]; printf("%s\n" , ans + 1); return 0; } qx[++r] = tx , qy[r] = ty; } } l ++ ; } return 0; }
相关文章
- GetKeyState和GetAsyncKeyState以及GetKeyboardState函数的用法与区别2-------C#检查键盘大小写锁定状态
- Flink中设置状态的超时
- ZOJ 2563 Long Dominoes(状态压缩DP)
- HDU 3920 Clear All of Them I(DP + 状态压缩 + 贪心)
- HDU 3006 The Number of set(位运算 状态压缩)
- POJ 1185 炮兵阵地(动态规划+状态压缩)
- HDU 4628 Pieces(DP + 状态压缩)
- 重新整理操作系统概念系类——进程状态与切换
- Atitit 命令指令的分类与权限 IMAP协议为例子 目录 1. 指令的作用的权限吧。 全局命令 未认证状态命令 未认证状态命令 选中状态指令2 1.1. 1.在任何状态下都有效的指令(全局命
- 【hiho一下 第九周】状态压缩·二
- Kubernetes pod状态出现CrashLoopBackOff 的原因
- hdu4336Card Collector 概率dp+状态压缩
- 关于SVN状态图标不显示的解决办法
- leaflet获取map当前状态(中心点,zoom值,角度边界值,容器宽高,像素边界值)
- UVA 1508 - Equipment 状态压缩 枚举子集 dfs
- POJ3254 Corn Fields 状态压缩DP
- 动态规划——dp[i]定义包含子状态,dp[i][2]这种,典型案例属于买卖股票,2表示 持有和不持有股票两种状态
- 传输层 TCP 三次握手中性能优化 SYN_RCV 状态/syn攻击
- ceph状态报:pgs not deep-scrubbed in time
- K8S集群中Pod资源处于Pending状态排查思路