「我们假设 b[0, i] 的最长可匹配后缀子串是 b[r, i]。如果我们把最后一个字符去掉，那 b[r, i-1] 肯定是 b[0, i-1] 的可匹配后缀子串，但不一定是最长可匹配后缀子串。」

========= 手动分割线 ========

对文中这句话，我的理解如下：

因为 b[i] 的约束可能导致 r 靠近 i，故去掉 b[i] 字符后，b[r, i-1] 虽然肯定是 b[0, i-1] 的可匹配后缀子串，但不一定是其中最长的。

例如：设模式串好前缀为 "abxabcabxabx"，其最长可匹配后缀子串为 "abx"，去掉最后的字符 'x' 后，虽然 "ab" 还是好前缀的可匹配后缀子串，但 "abxab" 才是最长可匹配后缀子串。

这句话虽然本身逻辑上是正确的，与上下文逻辑衔接性不强，感觉去掉这句更有利于对 next 数组第二种情况的理解。

终于看明白了，感觉设置了很多干扰项。其实用迭代思想解释就能理解了。
这个算法本质是找相等的最长匹配前缀和最长匹配后缀。
有两种情况，
（1）如果b[i-1]的最长前缀下一个字符与b[i]相等，则next[i]=next[i-1]+1.
（2）如果不相等，则我们假设找到b[i-1]的最长前缀里有b[0,y]与后缀的子串b[z,i-1]相等，然后只要b[y+1]与b[i]相等，那么b[0,y+1]就是最长匹配前缀。这个y可以不断的通过迭代缩小就可以找到

百度了下，终于搞明白了，回答自己前面一个问题。
关键是要搞明白k值是啥东西。
比如求aba 每个前缀最长可匹配前缀子串的结尾字符下标
这句话很容易引起歧义。
aba的前缀有a,ab, 后缀有ba,a 只有a与a匹配。 所以匹配的结尾下标是0.
abab 显然ab和ab可以匹配，所以匹配的结尾下标是1
abaaba 下标是2
ababa 下标是2
aaaa 下标是2

最难理解的是KMP算法了。
总体上，KMP算法是借鉴了BM算法本质思想的，都是遇到坏字符的时候，把模式串往后多滑动几位。
1.但是这里要注意一个细节，不然容易被前面学的BM算法给误导，导致难以理解。
BM算法是对模式串从后往前比较，每次是将主串的下标 ”i“ 往后移动多位。(这符合我们正常的思维，所以好理解)
KMP虽然也是往后移动多位，但是比较时，是对模式串从前往后比较；
对于主串已经比较过的部分，保持主串的 ”i“ 指针(即下标)不回溯。
而是通过修改模式串的”j“指针，变相地让模式串移动到有效的位置。(这里修改"j"，是让"j"变小了，我们说的还是将模式串往后移动，所以不太好理解)

2.KMP算法中不好难理解的，构建next数组，其实很简单，要多下自己的脑筋，不要被带偏了，就好理解了。就是求next[i](动态规划的思想，根据前面已经计算好的结果next[0]...next[i-1]来得到next[i])，前一个的最长串的下一个字符与最后一个相等，那next[i]就=next[i-1]+1；否则就需要找前一个的次长串，递归这个过程，直到找到或没有。

3遍才理解了差不多，还有一句话之前留言的还是木有理解，BM是去滑动主串，KMP是利用模式串的好前缀规则去跳过模式串（相当于滑动模式串）主串递增的形式。最难理解的就是next数组中的求解，如果b[0,i-1]的最长前缀是k-1 那b[0,k-1]就是最长的前缀 这里开始分两种情况，
第一种情况：b[0,k-1]的下一个字符b[k]=b[i],则最长前缀子串就变成b[0,k]，最长后缀就变成b[i-k,i]。next[i]=next[i-1]+1
第二种情况：b[0,k-1]的下一个字符b[k]≠b[i]，这时候我们要去寻找的就是b[0,i-1]中的最长前缀子串（最长匹配前后缀子串b[0,y] 和b[i-y-1,i-1]这两本身就是一一匹配的，而next数组记录的只有前缀我们仍然利用现有条件做推断）的最长可匹配前缀子串（必然跟后缀子串一致），就是b[0,i-1]的次长可匹配子串（划重点）（因为b[0,i-1]的最长可匹配子串c因为c这个串接下来一个字符跟b[i]不等，求取c它的最长可匹配子串一直到下个字符b[x+1]与b[i]相等递归求取）。
可能我说的跟理解的有点问题，举个例子： abeabfabeabe(主串) abeabfabeabc（模型串） 到e处不能匹配，最长可匹配子串就是 abeab接下来发现f与e不一致然后再求取abeab的最长可匹配子串 ， 为ab接下去的e刚好跟e匹配。

如果 next[i-1]=k-1，也就是说，子串 b[0, k-1] 是 b[0, i-1] 的最长可匹配前缀子串。如果子串 b[0, k-1] 的下一个字符 b[k]，与 b[0, i-1] 的下一个字符 b[i] 匹配，那子串 b[0, k] 就是 b[0, i] 的最长可匹配前缀子串。所以，next[i-1] 等于 k。

---------------

末尾应该是 next[i] 等于 k

// 求解 next 数组的简化版C++代码
// P 代表模式串 pattern，Next 是一个数组指针
// P[i,j] 表示模式串中下标从 i 到 j 的字符形成的子串
void getNext(int *Next,string P)
{
  Next[0] = -1; // 明显恒成立
  for (int i = 1; i < P.length(); i++) // 求解 Next[1]~Next[P.length-1]
  {
    int k = Next[i - 1]; // P[0,k] 是 P[0,i-1] 的最长可匹配前缀
    if (P[k + 1] == P[i]) // P[k+1]=P[i]，这种情况下最简单，说明 P[0,i] 的最长可匹配前缀为 P[0,k+1]
    {
      Next[i] = k + 1;
    }
    else // P[k+1]!=P[i]，说明 P[0,i] 的最长可匹配前缀不是 P[0,k+1]，此时寻找 P[0,i-1] 的次长可匹配前缀
    {
      while (k != -1 && P[i] != P[k + 1])
      {
        k = Next[k]; // 不断寻找 P[0,i-1] 的次长可匹配前缀
      }
      if (P[i] == P[k + 1])
      {
        Next[i] = k + 1;
      }
      else if (k == -1)
      {
        Next[i] = -1;
      }
    }
  }
}