use*_*312 17 string algorithm pattern-matching knuth-morris-pratt
KMP模式匹配算法的理论基础是什么？
我理解算法本身,但是,不明白Knuth,Morris和Pratt是如何发明这种算法的.
有没有数学证明？
你能给个链接吗？
tem*_*def 24
KMP匹配算法基于有限自动机,并通过隐式构建与字符串匹配的自动机的转换表来工作.使用非常聪明的线性时间预处理字符串进行搜索,可以构建匹配的自动机,然后可以在字符串上模拟自动机以在线性时间内搜索.最终结果是用于字符串匹配的线性时间算法.
构造的自动机通过为目前为止匹配的每个字符串数量设置一个状态来工作.默认情况下,转换是这样的,即匹配下一个字符前进到机器中的下一个状态,并且读取无效字符会转换回开头.但是,要搜索的字符串的某些部分可能会共享一些重叠结构,因此会添加一些新的转换,这些转换会在读取字符时将自动机恢复到较早(但不是第一个)状态.
该算法由Aho-Corasick算法推广,该算法构建更复杂的自动机,以便一次搜索多个字符串.
我在我的个人网站上实现了这个算法,其中包含对算法如何工作的实际细节的广泛讨论,包括正确性证明,算法背后更正式的直觉,以及如何从第一原理推导算法的解释.我花了一段时间才把它放在一起,但我希望它可以成为了解更多算法的好资源.
希望这可以帮助!