KMP算法

算法主要分为两部分：KMP、与next算法

KMP:本质是字符串的循环搜寻，不过在搜寻失败时通过next值来判断需要跳过多少个字符开始搜寻

int kmp_search(string str,string patt){
    int next=build_next(patt);
    
int i=0;//主串
int j=0;//子串
while(i<str.size()){
    if(str[i]==patt[j]){//单个字符匹配则后移
        i++;
        j++;
    }
    else if(j>0){//匹配到一半不匹配了，就根据next后移
        j=next[j-1];
    }
    else{//第一个就匹配失败了就直接移动主串
        i++;
    }
    if(j==patt.size()){//匹配完成
        return i-j;
    }
}

}

next：实质是一路遍历过来的前几个字符的相同前后缀的数量

int bulid_next(string patt){
    int next[patt.size()]={0};
    int prefix_len=0;//当前共同前后缀的长度，也可以看做前缀尾指针
    int i=1;
    while(i<patt.size()){
        if(patt[prefix_len]==patt[i]){
            prefix_len++;
            next.append(prefix_len);
            i++;
        }
        else{
            if(prefix_len==0){
                next.append(0);
                i++;
            }
            else{
                prefix_len=next[prefix_len-1];
            }
        }
    }
    return next;
}