kmp算法

#include<bits/stdc++.h>
using namespace std;
int nextval[1000];
//这里面所有的i和j都是序号
void get_nextval(string T){
    //j表示前缀的结尾，i表示后缀的结尾
    int i=1,j=0;
    nextval[1]=0;
    while(i<T.size()){
        if(j==0||T[i]==T[j]){
            i++; j++;
            //两个字符相同则跳过,这里进行了改进
            //优化点，防止T串为aaaab这种类型，需要一个一个往前翻，利用下面两行，可以直接找到最初等价位置
            if(T[i]==T[j]) nextval[i]=nextval[j];
            else nextval[i]=j;//T[i]!=T[j]
        }
        else{
            j=nextval[j];
        }
    }
}
int Index_KMP(string S,string T){
    //i是指向主串的指针，j是模式串的指针
    int i=1,j=1;
    while(i<=S.size()&&j<=T.size()){
        if(j==0||S[i]==T[j]){//持续比较后继字符
            i++; j++;
        }
        else{
            j=nextval[j];//模式串向右移动
        }
    }
    //如果j指针已经超出了模式串的末尾，则返回匹配成功的起始点
    if(j>T.size()) return i-T.size();
    else return 0;
}
int main(){
    string S,T;
    cin>>S>>T;
    get_nextval(T);
    cout<<Index_KMP(S,T)<<endl;
}

赏

谢谢你请我吃糖果