KMP弊端
因为kmp对cache不友好,也较难使用simd(单指令多数据的并行计算)优化,而且实际上的字符串很难跑到O(nm),所以实践上朴素算法可能更快.
自动机科技
自动机是一个确定的数学模型,对于信号序列(字符串)的某种性质给出是或不是的回答(确定有限状态自动机).然后自动机上每个节点都会有对了如何错了如何的判定,所以自动机实质上是一张有向图.
AC自动机及其魔改
AC自动机的板子是计算多个字符串在一个字符串的匹配情况.最裸的板子是求多个小串在一个一个长串之中各自出现了多少次,时间复杂度 $O(|T|+\sum|S|)$ ,然而肯定会有魔改的版本…
子序列自动机(简单字符集)
快速判定某些字符串t是不是母字符串s的子串, $O(s+\sum t)$ .
就是一个dp.设字符集为S,开一个dp[len][|S|]表示当前len的位置的下一个S的字符在哪里,从后往前推复杂度O(lenS).
子序列自动机(复杂字符集)
上面的子序列的dp和字符集长度挂钩,如果S很大时间空间都会爆,考虑更优解法.
发现nxt只会每次更新只会改一个点,所以能够使用主席树优化,具体地,对值域开一个桶,对字符串长度开根的长度,然后添一个log进行建树和匹配.
另解 :使用vector桶存值域,然后值域二分找到下一个位置,然后跳转即可,复杂度依然是log.
字符串拼接
经常见到字符串拼接求最小字典序的题,在此总结一下.
cf632cp1012n个字符串拼一个字典序最小的字符串,只能用一次
直接排序: (a+b)<(b+a)
这是一个结论,原理在此不表,可以看洛谷关于这个题的题解.
abc416gn个字符串用m个拼,每个字符串无限次使
首先,相同长度直接取字典序最小的.
所以如果字符串为无穷,那么一定是上文排序最小的字符串来回重复.
但不无穷的时候,后缀会出问题,例如:1
2
3
43 2
cba
cb
c
答案`1
cbac
发现字符串拼接的性质为若 $A<B$ 则 $C+A<C+B$ ,但是若 $A<B$ 并没有 $A+C<B+C$ .
所以考虑倒序计算:当前答案为空,每次往最前加一个字符串比较,如果一直加最小的字符串那么可以推定剩下的一定是最小字符串的来回重复.
可以使用dp,在有限范围内求解.
abc225fn个字符串选m个拼字典序最小的字符串,只能用一次
dp.首先排序,保证叠加时候的顺序.
由于前面说的性质,只能设 $dp[i][j]$ 为i及以后的字符串里选j个的最小值,那么可以直接dp了.
abc434fn个字符串拼一个字典序第二小的字符串,只能用一次
首先排序,瓶颈在于lcp和哈希,在此不表.
得到字典序最小的元素后考虑微调后成为答案:
如果存在X和Y满足XY=YX,那么他们两个交换之后答案不变.
有可能是sn和sn-1交换,也有可能是sn-1和sn-2交换,只有这两种情况.(可以见证明)
关于如何排序:
shuffle之后暴力即可,或使用字符串哈希+二分