[Water]水之字符串问题专版

【字符串】(挖掘性质)

KMP

在长度为的串中,设标号为.
令以第个字符开头的长度为的字符串为.
设长度为的字符串为空。

通俗的讲,表示原串长度为的前缀的最长的前后缀相等的长度(严格小于)。
这有什么作用呢?
考虑文本串,模式串,询问
朴素的暴力算法的时间复杂度为.
思路是:依次枚举文本串的每一个位置,尝试作为模式串的起点位置,并用的时间复杂度判断是否匹配。
但是这样实在是太慢了。
我们不妨设计一个转移方程,设表示文本串的长度为的前缀的最长后缀长度,使得这个后缀是模式串的前缀。
那么问题转化为求.
有一个显然的转移:.
那么反之呢?暴力吗?显然不用。


考虑,也就是说至少文本串中以结尾长度为的串和模式串中长度为的前缀是完全相同的。
考虑之前已经假设计算出来的模式串数组,则模式串中长度为的前缀的长度为的前缀和后缀完全相同。
那么我们知道文本串中以结尾长度为的串的长度为的后缀和模式串中长度为的前缀完全相同。
比如下图中三段黄色的串全部相同。

那么问题转化为了比较,如果相同可以得出,如果再失配?
我们发现这个问题是一个和开始的问题完全类似的子问题。
所以和上面做法类似,再缩短当前匹配长度,去比较
这样直到匹配或者不存在继续迭代的指针(也就是0)。
直到不存在指针也找不到的话,显然.
通过以上方法可以递推计算出那么这个问题已经解决了.
那么剩下的问题是:我们如何计算出模式串数组呢?
考虑套用之前的算法:假设我们知道了,那么如何求出呢?
将模式串长度为的前缀看作新模式串,将模式串长度为的前缀看作新文本串,那么现在我们要做的事情就是,已知,以及新模式串的全部数组,求解,显然用刚才的方法就可以了.
为什么有这些相等关系呢?联系的定义就能弄明白了。
从而我们完美地解决了这个问题。
顺便提一下:你能很快对于一个字符串在的时间复杂度内求出所有的长度,满足这个字符串长度为的前缀和长度为的后缀完全相同吗?
NOI2014动物园
@
做法的线性证明。
@

Trie树

就是所谓的前缀树。
根到某个节点的有向路径,表示某个字符串的前缀。
通常在表示字符串结尾的节点加权。

AC自动机 && Trie图

后缀数组

后缀自动机

Manacher算法(最长回文半径)

Hash大法

假如有
let
那么以l开头长度为len的子串hash值为
暂时刷了一个题发现seed选取很有学问。。。暂时把坑放在这里。

comments powered by Disqus