首页 > 代码库 > 字符串匹配：从后缀自动机到KMP
字符串匹配：从后缀自动机到KMP
后缀自动机(sam)上的字符串匹配
====
我们把相对较短的模式串构造成sam。
对于P="abcabcacab", T[1..i]的后缀，使得它是sam的最长前缀长度:
T: b a b c b a b c a b c a a b c a b c a b c a c a b c
1 1 2 3 1 1 2 3 4 5 6 7 1 2 3 4 5 6 7 5 6 7 8 9 10 4
如果最长前缀长度是|P|，则表示T[1..i]的后缀和P匹配。
内存使用
可能多个trans指针同一个节点，因此像删除树那样会引起double-free:
为此我们暂时采用内存池的做法。
如果扩展到包括数字和空格，则需要表示37个转移指针。
KMP算法
====
给定模式串P,文本串T,
假设在s位置已匹配了q个字符, 即P[1,..,q]=T[s+1,..,s+q], 而在P[q+1]不匹配。
strstr()这时会把指针指向s+2,从P[1]重新开始匹配。
当时Knuth,Morris,Pratt就想可不可以把指针再移远一点。
假设有P[1,..,k]=T[s+q+1-k,..,s+q],这时从P[k+1]开始比就行了，显然我们希望k越大越好，对应地指针移动增量=q-k越小，因此应该不会错过某些完全匹配的位置。
我们把上面两个等式合并，得到P[1,..,k]是P[1,..,q]的后缀。问题变成：
对于每个q, 求P[1,..,q]的最长的真前缀（长度记为k)，同时它也是P[1,..,q]的后缀。
我们定义前缀函数pi(q):=k.
如何计算pi(q) ?
====
使用递推的想法，假设我们已经计算好了pi(q)=k。
如果P[k+1] = P[q+1], 则显然有pi(q+1) = k+1；
否则，看作是一个匹配问题, 我们来看pi(q)的含义是与P[1,..,q]末尾匹配的最长前缀长度k，我们就拿这个前缀来匹配，并期望P[k+1]和P[q+1]一样，否则k=pi(k)循环下去。
初始条件:pi(1) = 0， 因为最长真前缀是空串。
当前P[1,..,k]匹配T[q-k+1,q]，而在T[q+1]不匹配，
应用前缀函数的定义，应该从位置s+1-k + q-k =
一个字符串P[1,..,j]去匹配P[q+1-j,..q+1]的过程。
k=pi(k), 直到P[k] = P[q+1]。
如何做线性的字符串匹配？
====
参照后缀自动机的做法， 我们把pi和P组成一个自动机，T在这个自动机上
走一遍。
前缀函数练习题目：
1. P 在T中的出现次数? 提示：检查pi(PT)
2. (ab)^3 = ababab, 如何求最大的重复因子r=3?
====
我们把相对较短的模式串构造成sam。
对于P="abcabcacab", T[1..i]的后缀，使得它是sam的最长前缀长度:
T: b a b c b a b c a b c a a b c a b c a b c a c a b c
1 1 2 3 1 1 2 3 4 5 6 7 1 2 3 4 5 6 7 5 6 7 8 9 10 4
如果最长前缀长度是|P|，则表示T[1..i]的后缀和P匹配。
内存使用
可能多个trans指针同一个节点，因此像删除树那样会引起double-free:
为此我们暂时采用内存池的做法。
如果扩展到包括数字和空格，则需要表示37个转移指针。
KMP算法
====
给定模式串P,文本串T,
假设在s位置已匹配了q个字符, 即P[1,..,q]=T[s+1,..,s+q], 而在P[q+1]不匹配。
strstr()这时会把指针指向s+2,从P[1]重新开始匹配。
当时Knuth,Morris,Pratt就想可不可以把指针再移远一点。
假设有P[1,..,k]=T[s+q+1-k,..,s+q],这时从P[k+1]开始比就行了，显然我们希望k越大越好，对应地指针移动增量=q-k越小，因此应该不会错过某些完全匹配的位置。
我们把上面两个等式合并，得到P[1,..,k]是P[1,..,q]的后缀。问题变成：
对于每个q, 求P[1,..,q]的最长的真前缀（长度记为k)，同时它也是P[1,..,q]的后缀。
我们定义前缀函数pi(q):=k.
如何计算pi(q) ?
====
使用递推的想法，假设我们已经计算好了pi(q)=k。
如果P[k+1] = P[q+1], 则显然有pi(q+1) = k+1；
否则，看作是一个匹配问题, 我们来看pi(q)的含义是与P[1,..,q]末尾匹配的最长前缀长度k，我们就拿这个前缀来匹配，并期望P[k+1]和P[q+1]一样，否则k=pi(k)循环下去。
初始条件:pi(1) = 0， 因为最长真前缀是空串。
当前P[1,..,k]匹配T[q-k+1,q]，而在T[q+1]不匹配，
应用前缀函数的定义，应该从位置s+1-k + q-k =
一个字符串P[1,..,j]去匹配P[q+1-j,..q+1]的过程。
k=pi(k), 直到P[k] = P[q+1]。
如何做线性的字符串匹配？
====
参照后缀自动机的做法， 我们把pi和P组成一个自动机，T在这个自动机上
走一遍。
前缀函数练习题目：
1. P 在T中的出现次数? 提示：检查pi(PT)
2. (ab)^3 = ababab, 如何求最大的重复因子r=3?
3. 如何在线性时间内判断是否为循环移位，比如arc和car。（这个我还不知道怎么做）
<script src="https://code.csdn.net/snippets/422732.js" type="text/javascript"></script>
KMP比SAM节省内存：
<script src="https://code.csdn.net/snippets/422737.js" type="text/javascript"></script>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。