好久没写了,正好趁着晚上这个空,把KMP打了出来,发篇博客吧!

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
int Next[maxn];
void getNextArr(string s){
    if (s.length() == 1){
        Next[0]=-1;
    }
    memset(Next,0,sizeof(Next));
    Next[0] = -1;
    Next[1] = 0;
    int i = 2;
    int cn = 0;
    while(i < s.length()){
        if(s[i - 1] == s[cn]){
            Next[i++] = ++cn;
        } else if (cn > 0){
            cn = Next[cn];
        } else {
            Next[i++] = 0;
        }
    }
}
int getIndexOf(string str_1, string str_2){
    if (str_1.empty() || str_2.empty() || str_2.length() < 1 || str_1.length() < str_2.length()){
        return -1;
    }
    int index_1=0,index_2=0;
    getNextArr(str_2);
    while (index_1 < str_1.length() && index_2 < str_2.length()){
        if(str_1[index_1] == str_2[index_2]){
            index_1++;
            index_2++;
        } else if (Next[index_2] == -1){
            index_1++;
        } else{
            index_2=Next[index_2];
        }
    }
    return index_2 == str_2.length() ? index_1 -index_2 : -1;
}
int main(){
    string str_1,str_2;
    cin>>str_1>>str_2;
    cout<<getIndexOf(str_1,str_2)<<endl;
    system("pause");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注