[HNOI2006]最短母串问题 --- AC自动机 + 隐式图搜索
[HNOI2006]最短母串问题
题目描述:
给定n个字符串(S1,S2.....,Sn),要求找到一个最短的字符串T,使得这n个字符串(S1,S2,......,Sn)都是T的子串。
输入格式:
考虑T匹配了所有的S串,这相当于一个状态
考虑状压,将已经匹配了多少S串压成一个状态。
\(dp(i,j)\)表示当前到了 i 号节点(AC自动机中),匹配的情况是 j
不难发现,要寻找的是距离状态\(dp(0,0)\)转移次数最少的点。
因此,可以考虑用隐式图搜索bfs来代替直接dp
怎么转移?
我们需要知道到达每个节点已经匹配了哪些点。
因此,让所有串在AC自动机的尾端逆着fail树给予状态。
转移比较好想,\(dp(i,j) ---> dp(v,j | state(v))\)
当我们第一次到达状态\(dp(..., 2 ^ {n} - 1)\)时,意味着我们已经构造出了一个串。
听起来没有什么问题。
但题目有个诡异的要求:字典序最小。
这对于bfs来说并不难构造,优先走'A'扩展,再'B'......
这样,字典序一定是最小的。
现在解也出来了,怎么往回找来得出这个串呢?
因此,额外记录一个\(pre(i)\)表示 i 号状态被转移的状态,\(letter(i)\),表示 i 号状态被转移的字母。
往回一直搜到初始状态即可。
完了吗?
并没有,本题还有卡空间的恶心条件。
我承认,我真不知道怎么卡,看了下题解(......)
1.用stl的队列,空间消耗是随时的。
2.用\(vis(i, j)\)来表示\((i,j)\)这个状态有没有被搜索过,如果有,就不再加入队列。
然后注意一下,我的实现出了点小差错。
后来发现是AC自动机中一个点可能是很多串的结尾,因此预处理转移状态时,要根据串的不同状压,而不是单一的赋值。
细节可以自己思考思考。
最新文章
- SparkStreaming实现Exactly-Once语义
- dict与list的in 操作的速度
- Python之import
- 【BZOJ-3996】线性代数 最小割-最大流
- Springmvc4 com/fasterxml/jackson/core/JsonProcessingException
- Hadoop入门进阶课程4--HDFS原理及操作
- iOS闹钟实现
- Jquery简单动画的实现记录
- Python爬虫 Cookie的使用
- 关于QT按键信号槽的总结(原创)
- 安装Apache Maven
- JavaScript 轮播图实例
- Flask入门之SQLAlchemy配置与数据库连接
- 痞子衡嵌入式:常用的数据差错控制技术(1)- 重复校验(Repetition Code)
- 【算法】LeetCode算法题-Longest Common Prefix
- 解决idea下载依赖包慢到出奇
- SPI 核软件调试记录
- React笔记-事件分发
- Spring 多数据源事务配置问题
- Windows下Visual Studio 2013编译Lua 5.2.3