读书笔记 - 字符串匹配

KMP 算法

利用 dfa 状态机。

对于长度为M的模式字符串和长度为N的文本,KMP算法查找算法访问的字符不会超过M+N个。

KMP算法为最坏情况提供的线性级别运行时间保证是一个重要的理论成果。在实际应用中,它比暴力算法的速度又是并不十分明显,因为极少有应用程序需要在重复性很高的文本中查找重复性很高的模式。

Boyer-Moore算法

Boyer-Moore 从右向左扫描字符串。

Rabin-Karp 指纹字符串查找算法

查找多个字符串匹配。