首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

KMP算法的数学原理(优化版)

对于一个有限自动机M,它是一个5元组(S,s₀,A,Σ,δ),S是有限状态集,s₀是初始状态(x₀∈X),A是可接受状态集(A⊆X),∑是有限输入表,δ是状态转移函数(从S×Σ到S的映射)。假定有一个模式串p="abaabcb"(长度m),待匹配字符串s="abaabaabcb"(长度n),当第5个字符'c'匹配失败时,寻常的做法是将p的索引回退到0,s的索引回退到1,再重新进行匹配。观察s与p得知:p0...4==s0...4,p0...1==p3...4=="ab",当s5与p5无法匹配时,可以尝试判断s5==p2是否成立,若成立,由前面的推论可知p0...1,2==s3...4,5,所以第5个字符匹配失败时,可以将p的索引回退到2继续进行比较,这样就无需变动s的索引,节约了计算时间,所以只要能够为状态机设计出合理的状态转移函数,就能够加速字符串的匹配。

05
领券