【3】4 KMP算法思想

KMP 算法： 朴素模式匹配算法的优化！

 

 

 

 朴素模式匹配算法缺点:
当某些子串与模式串能部分匹配的时候，主串的扫描指针 i 经常回溯，导致时间开销增加！

 

 

 

分析：
oo  都是o 开头，肯定不匹配，然后 g 开头但是紧跟 l  所以也不行， l 开头的也不匹配！ 所以不需要像朴素模式匹配算法那样从 g 后面一个一个验证！

 

 

 

 

oogl 开头的不用考虑，那么接下来能够配对上的情况是：如果这个问号是 g，然后后面说不定就是 oogle 呢。
用代码描述这个过程的话，就相当于 主串扫描指针 i 依然指向 ？  但是模式串的扫描指针 g 指回第一个字母！ 
 

==> 这个就是 KMP 算法的优化思路，即尝试着让主串的指针 i 不回溯，只有模式串的 j 会回溯！

 

 

 

如果是朴素模式匹配算法，每次相当于模式串右移一步！   

 

 

如果是 g 则需要 i++  和  j++操作！

 

 

如果不是g   则 j 不动， i++。

 

 

 

 

下一种情况！

因为之前只是判断了 不是 l, 但是不是 o 并不知道，所以需要 j 从2开始验证。

 

 

 

 但其实这里已经检测出不是 g 了，所以这种方案并不是一个最优的方案，会导致进行一次没有必要的对比，但是相比朴素模式匹配已经少对比了两次，这种特殊情况暂时不考虑。 

 

 

 

 

相比于朴素算法，少对比了一次！

 

 

 

 

 

 

 

 

 

在 int next[7] 中  为1的时候设置为了 0 ， 这一步的操作主要为了代码实现： 先令 j=0   然后让 i 和 j  同时++ .  这样就可以让指针 i 后移一位，然后让指针 j 也保持为 1 这个值！ 

 

 

 

==>  所以 KMP 算法的关键在于 搞出一个和模式串相对应的数组 next !

有了  next 数组之后，就可以将朴素模式匹配算法把它改造成 KMP 算法！

 

 

 

当 j 等于 0 的时候，就说明主串的指针 i 也应该往右移动了！
当 i 和 j 指向的两个字符相等时， i  和 j 也应该同时往后移。