字符串匹配算法（KMP）

两个字符串A、B，在A字符串中查找B字符串（分别长为m,n），如果找到了，返回B字符串在A字符串中第一次出现的下标。

暴力的方法是在A[k]，从k=0开始对比B字符串汇中的字符，如果失败了，那么k++，时间复杂度为mn。
这种算法忽略的B字符串中特性，也就是说，只向后移动一位对就开始对比，实际中，可能需要移动的位数更多。

所以，需要先找一下规律，当在A[k]出对比B字符串失败后，应该向后移动多少位（也就是A[k+?]），开始对比？

引入一个概念：字符串前后缀最大相同长度
也就是一个字符串，如果前面n位和后面n位字符完全相同（顺序一样，不是镜像）。那么n就是字符串前后缀最大相同长度（名字不要在意，别的都是公共部分，我觉得别扭）。假设该字符串长为m,那么n的取值范围为0~m，也就是说这个前缀和后缀可以重叠，可以完全重叠。

假若，在A[k]中匹配B，在B[h]开始不同，那么直接向后移动B字符串前h位的前后缀最大长度（以后都称为next[h]）既可。
当在B[h]匹配失败后，B[h-next[k]]到B[h]的字符串（前缀）与B[0]到B[next[k]]的字符串（后缀）是相同的，在A中对应的位置也是相同的。此时，只需要将B[0]移动到B[h-next[h]]位置，移动后，B在A中的前next[h]位是已经匹配好的。所以不需要再从B[0]开始匹配了。

为什么可以跳过这么多的位置，重要的要理解next[]的构造过程。

构造过程之这样子的：
next从下标1开始存储，因为B从开始到结束，子字符串长度为0没意义。当子字符串长度为1是，next[1]=1。

假设当子字符串长度为k时(也就是B[k-1]以及之前)，前后缀最大相同长度为m。

子字符串长度为k+1：当B[k]=B[m+1]时 ，（B[k]为之前的后缀之后的第一个字符，B[m+1]是前缀之后的第一个字符，如果相等，就是前后缀最大相同长度+1），所以next[k+1]=next[k-1]+1。

不想等时：开始比较B[m]位和B[k]位，如果相等也就是，之前的后缀和前缀，在后面有公共部分。其相同长度可能为next[m]+1，因为B[m-1]子字符串的前缀的后一位可能不等于B[m]。如果相等，那么next[k]=next[next[k]]+1
否则，再比较B[m-1]和B[k]，同上。

#include <vector>
#include <iostream>
#include <string>

using namespace std;


vector<int> calNext(const string &str)
{
    int len = str.size();                                   //总长度
    vector<int> next(len + 1);
    next[2] = 0;
    int sublen;                                             //要计算next的子字符串
    for(int i = 2; i < len ; i++)  
    {
        sublen = i+1;
        if(str[i] == str[next[sublen-1]] )                  //sublen - 1 上一个子字符串长度
        {                                                   //next[sublen - 1] 上个子字符串前缀的后一位
            next[sublen] = next[sublen-1] +1;
        }else{
        
        //B子字符串前缀右移，以此比较其前缀与str[i]
        for(int j = next[sublen-1] -1  ; j >= 0; j--)         
        {
            //比较子字符串前缀与str[i]
            if(str[next[j]] == str[i])
            {
                //如果子字符串前缀后一位与str[i]相同
                //那么比较以前缀为子字符串的前缀的后一位与str[i]
                //这样就还是比较了一个子字符串的前缀和后缀与待计算next的字符
                if(str[next[next[j]-1]] == str[i])
                //上面的-1,是将长度转化为下标，next中的都是下标
                {
                    next[i+1] = next[next[j]]+1;
                    break;
                }
            }
        }
        }
    }
return next;
}

int main()
{
    string str("ABCKACBACLABKJ");
    str="abaabcaba";
    vector<int> next = calNext(str);

    for(int i = 1 ;i < next.size();i++)
    {
        cout<<next[i]<<" ";
    }
    cout<<endl;
}

这就是next的构建，其基本思想是：
比较一个子字符串的前缀后一位和后缀后一位与待计算next字符，如果一样，那么待计算字符的next值就是子字符串的next值+1.
现在next中存储的就是每次跳转的时候额外跳转的歩数，同时也是跳转以后搜索的起点。