[算法系列之十四]字符串匹配之Morris-Pratt字符串搜索算法

前言

我们前面已经看到，蛮力字符串匹配算法和Rabin-Karp字符串匹配算法均非有效算法。不过，为了改进某种算法，首先需要详细理解其基本原理。我们已经知道，暴力字符串匹配的速度缓慢，并已尝试使用Rabin-Karp中的一个散列函数对其进行改进。问题是，Rabin-Karp的复杂度与强力字符串匹配相同，均为O(mn)。我们前面已经看到，蛮力字符串匹配算法和Rabin-Karp字符串匹配算法均非有效算法。不过，为了