KMP 与 AC自动机
都是字符串匹配
KMP是单模匹配
ac自动机是多模匹配
KMP原理
例子
当我们匹配字符串A(长度为n)中是否有B(长度为m, m<n)的时候
比如:
- A
ABCDABCDEF - B
ABCDE
一个朴素的思路是暴力, 复杂度当然是O(n * m)
KMP就是一个优化的算法
KMP的理论基础就是, 并不是每次匹配往后跳一位. 而是跳多位(>=1).
当匹配到ABCD, 发现下一位并不是E的时候, 我们可以直接跳到下一个ABCD, 主串和模式串都可以不需要从头开始比较. 这个优化是不是很直观
为什么可以这么做呢? 因为比如逐位比较到第k位的时候, 前k-1个字符是我们已知的. 如果我们能利用这个信息就好了! 事实上我们确实可以利用这个信息
如何做
这实际上是一个dp
一个状态转移
我们假设主串是
a b c d e f g h i j k
而模式串是x y z w
继续假设此时我们已成功匹配了两个字符, a == x, b == y, c == z, 但是第4个字符 w != d
- 想要往后跳
此时我们想要跳, 往后跳尽量远的距离, 就可以尽量降低复杂度 - 怎么跳
一个朴素的想法是跳到下一个"a b c" 连接的地方, 既然这个"a b c"处失配了, 那就跳到下一个, 然而, 这种思路其实就是一个一个的朴素匹配. 预处理的时间跟直接朴素匹配一样, 都是无法接受的.
那咋办嘛. 所以这里重点不是如何预处理主串, 因为我们算法实际上是在主串跑的, 预处理主串的复杂度是我们无法接受的.
主串一定是和子串匹配失败时候才需要跳, 那就意味着至少有一段(0<=len<m)的部分是和子串前len部分是一致的, 这样就有了操作的空间. 于是很直接地想到了预处理子串. 有什么比只需要处理m长度的串就可以进行跳跃更有性价比呢? - 跳的思路
现在的已知信息就是, 在主串的[x, x + len)的串和子串的[0, len)是一致的
跳跃是产生在主串上的
这时候又可以回到刚才朴素的想法了, 我失配了, 我想尽量往后跳啊,
s = "xyz" 匹配成功, 尽量往后跳的话, 我会想在主串里找到下一个"xyz", 然后从那里继续跟子串的第一个"xyz"对齐, 继续比较
可根据刚才说的, 我们现在只拥有子串的预处理结果. 而当前根据我们的已知信息,
主串的xyz的串和子串的xyz是一致的
这有个毛线用 (- _ -) , 我们完全无法找到下一个"xyz"在哪
故而, 我们可以发现, 既然要找第二个一样的string, 匹配里就要有重复的string, 这样才行 - 跳
现在我们重新假设现在的匹配是这样的:
主串:
"x y z x y ? x y z x y w"
模式串:
"x y z x y w"
当'?'和'z'失配的时候, 已匹配的部分是"x y z x y", 失配的部分是 '?' != 'w'
是不是可以跳?
有重复的吧?
是不是主串可以从第二个"x y"跳到第一个"x y"?
和不现实的预处理主串相比, 是不是就是把朴素跳跃思路放到了预处理模式串上? - 为什么要跳最长公共前后缀
再假设是这么一个串
主串:
"x y z x y t ? x y z x y t w"
模式串:
"x y z x y t w"
和刚才相比多了个t
跳跃的时候怎么跳? "x y"可以直接跳第二个"x y"吗?
no! no! no! だめ!
可以注意到, xyt 和 xyz 已经是无法匹配状态了, 所以跳的毫无意义
同理, x 和 x 也没法跳, y 和 y 也没法跳
这下明白为什么next数组是 最长相同前后缀 了吧？
因为前后缀在无法跳(没有相同前后缀)的情况下, 其他相同的可以证明是无法跳的
而当前后缀可以跳的时候, 则一定是最优跳法, 比如xyxyx, 跳个xyx不比跳个单独的x更优吗
next数组的计算
朴素思路起手
i属于[0, m), 对于每一个区间[0, i]
暴力双指针指向两边, 匹配一遍
实际上这里有一个优化, 比较难想, 是依赖于对称性的
其实是这样的
首先, 朴素匹配的基础是没问题的. 大部分case遇不到相等于第一个元素的case直接就越过去了, next是-1
一旦进入next有非-1值的情况, 也就是我们就可以依赖于前一个求出来的next状态的情况
举个例子就是"abc??abc", 计算最后一个c的时候其实就可以基于ab已经匹配的状态+1, 1+1 = 2直接出答案
而再来个case, 当失配的时候怎么搞
s = "ababc??ababz"
这里是从第6个字符直接开始匹配的, 而z和c失配了, 并不是直接从头再来, 而是从前一个"b"的next来, 注意这里的b指的是s[3]的那个'b', 因为后面的b的next存的肯定是3不是么...
而s[3]的b的next就回滚到了第一个"ab", 意识到了吗, 截短了, 既然"ababz"不匹配"ababc", 那就用"abz"去尝试匹配"aba", 不成功就继续回滚
在有大量重复子串的数组里, 这样处理可以显然提高效率, 类似的技巧还出现在manacher求回文串里
自动机
ac自动机是用tire树
加了个失配指针, 原理很类似, 多模匹配的这些目标串, 前缀相同的越多, 匹配起来越容易
我没仔细看回文自动机, 感觉原理应该也类似?