- 复杂度来源于状态需要有更多维去表示，当状态数量过多的时候， 还需要对状态进行压缩。
- 状态转移方程更加复杂， 更不容易想出。
在朴素算法中，我们需要挨个比较所有字符，才知道目标字符串中是否包含子串。那么，是否有别的方法可以用来判断目标字符串是否包含子串呢? 答案是肯定的，确实存在一种更快的方法。为了避免挨个字符对目标字符串和子串进行比较，我们可以尝试一次性判断两者是否相等。因此，我们需要一个好的哈希函数(hash function)。 通过哈希函数，我们可以算出子 串的哈希值，然后将它和目标字符串中的子串的哈希值进行比较。 这个新方法在速度上比暴力法有显著提升。
KMP算法(Knuth-Morris-Pratt)的思想就是，当子串与目标字符串不匹配时， 其实你已经知道了前面已经匹配成功那 一部分的字符(包括子串与目标字符 串)。以阮一峰的文章为例，当空格与 D 不匹配时，你其实 知道前面六个字符是 “ABCDAB”。KMP 算法的想法是，设法利用这个已知信息，不要把“搜索位置” 移回已经比较过的位置，继续把它向后移，这样就提高了效率。