Python中KMP算法如何从BF字符串匹配算法演变，实现高效匹配？

本文共计4047个文字，预计阅读时间需要17分钟。

1. 字符串匹配算法所谓字符串匹配算法，简单地说就是在目标字符串中查找是否存在另一个子字符串。例如，在字符串ABCDEFG中查找是否存在子字符串EF。

可以将字符串ABC与目标字符串进行匹配。

1. 字符串匹配算法

所谓字符串匹配算法，简单地说就是在一个目标字符串中查找是否存在另一个子字符串。如在字符串 "ABCDEFG" 中查找是否存在 “EF” 字符串。

可以把字符串 "ABCDEFG" 称为原始（目标）字符串，“EF” 称为子字符串或模式字符串。

本文试图通过几种字符串匹配算法的算法差异性来探究字符串匹配算法的本质。

常见的字符串匹配算法：

• BF（Brute Force，暴力检索算法）
• RK （Robin-Karp 算法）
• KMP （D.E.Knuth、J.H.Morris、V.R.Pratt 算法）

2. BF(Brute Force，暴力检索)

BF 算法是一种原始、低级的穷举算法。

2.1 算法思想

下面使用长、短指针方案描述 BF 算法：

1. 初始指针位置： 长指针指向原始字符串的第一个字符位置、短指针指向模式字符串的第一个字符位置。这里引入一个辅助指针概念，其实可以不用。