我对KMP 算法的理解

    假设现在我们面临这样一个问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？

    如果用暴力匹配的思路，并假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有：

• 如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；
• 如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。

以上是暴力算法。既然我们已经判断了那么多了，为啥不利用之前判断的结果呢？例如：

情况1

aaabcabcabd  j == 7

    abcabd        i == 5

到底倒退多少合适？上面这个例子其实 S[7] != P[5]，这个时候可以发现S[5-7] == P[0-2] 其实可以i - 2就可以开始下一次判断了，不用移动j的位置。

再看看下面例子

情况2

aaabaabcabd

  aabc

s[4] != p[3] 这个时候can't j++ i++, just set i =0;

情况3

最常见的情况就是s[i] != p[0] then i++, p = 0;

那我们就有三种情况要考虑

有了这三种情况，我们还要一个辅助的东西去知道倒退多少，容易想到的是一个预处理数组，在下问为next[];

p[] = abcabdabca;

初始化next[p.size] 为0

but next[0] = -1; 

保留一个计数位置i = 0，一个计数位置j ，初始化位置是1

 a  b  c  a  b  d  a  b  c  a

-1 0  0 -1 0  2  -1 0  0  0

if (p[i] == p[j])

{

       next[j] = next[i];

       i++;

       j++;
}

else{

       next[j] = i;

       i = 0; 头计数clear，重新开始扫描

}