假设我们有这样一个要求,一个字符串S,一个匹配字符串P,我们想知道匹配串P是否被包含在字符串S中,如果包含那它在S的什么位置上?...按这样的思路D.E.Knuth,J.H.Morris和V.R.Pratt 三人一起提出了一种新的算法,也就是著名的KMP算法.KMP算法的主要思想是:
1. 字符串指针不回溯
2....,没有实际意义
那我们重新来看下使用了KMP算法的匹配过程
1....匹配成功
总结一下,通过辅助数组next[],确定整体匹配过程中,匹配串P的某个元素该与字符串S匹配,避免字符串S的指针回溯;
利用辅助数组next[],确定匹配失败时,后续匹配串该如何移动和重新比较,...留个疑问,注意观察第4行匹配过程,看看这个next算法是否就是最合理的呢?我们下一节在来讲这个next算法的优化.