KMP算法的优点：时间复杂度为O(N+M)比简单暴力的O(NM)快

算法的过程：在目标子串与待查串中分别设置指针i，j，进行比对，每成功一次两个指针加一，在比对不成功时，对待查串中的指针回退到next[j-1]这个位置

为什么要用kmp算法：例如，在字符串"aaaaab"中匹配"aaab"这个字符串，暴力算法在匹配到b时会让指针回退到1，层层比对；而kmp算法中，i会变为2(next[2]=2)，且kmp算法中指针永不后退，这就大大提高了查找的效率

我们通过两个函数来实现该算法

第一个：计算next数组的函数

void computenext(string s,vector<int>&next) {
    int length=0;
    int i=1;
    int m=s.size();
    while (i<m) {
        if (s[i]==s[length]) {
            length++;
            next[i]=length;
            i++;
        }else {if (length!=0) {
                length=next[length-1];
           }else{next[i]=0;i++;}
        }
    }
}

该函数主要对字符串s的字串进行匹配，其中i的位置就代表了正在进行匹配的时字符串s的前i个字符组成的字符串，其中，length=next[length-1]即为kmp算法的重点，在没找到时，并不回溯到0，而是回溯到next[length-1]重新匹配；

接下来只需要构造一个函数进行KMP算法的匹配即可，代码如下

int KMP(string targets,string son) {
    vector<int>next(son.size(),0);
    computenext(son,next);
    int i=0;//targets指针吗
    int j=0;//son指针
    while (i<targets.size()){
        if (targets[i]==son[j]) {
            i++;
            j++;
            if (j==son.size()) {
                return i-j;
            }
        }
            else {
                if (j!=0) {
                    j=next[j-1];
                }else i++;
            }
        }
    return -1;
}

利用computenext函数计算出next函数的值，再对字符串进行匹配即可，该函数在匹配成功时返回i-j即为匹配位置，匹配不成功时进行下一个子串的匹配，直到完全不成功时返回-1；