KMP算法

本文主要是介绍KMP算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#include <bits/stdc++.h>

using namespace std;

char ch1[1000005];
char ch2[1000005];
int Next[1000005]={0};

int buildnxt(int x,int y)
{
    if(y<0) return 0;
    if(ch2[Next[y]]==ch2[x]) return Next[y]+1;
    return buildnxt(x,Next[y]-1);
}

int main(){
    cin>>ch1>>ch2;
    int len1=strlen(ch1);
    int len2=strlen(ch2);
    for(int i=1;i<len2;++i){
        Next[i]=buildnxt(i,i-1);
    }
    int tar=0,pos=0;
    while(tar<len1){
        if(ch1[tar]==ch2[pos]){
            if(pos==len2-1){
                cout<<tar-pos+1<<endl;
                pos=Next[pos];
            }else{
                pos++;
            }
                tar++;
        }else if(pos){
            pos=Next[pos-1];
        }else{
            tar++;
        }
    }
    for(int i=0;i<len2;++i){
        cout<<Next[i];
        if(i<len2-1) cout<<" ";
    }
    return 0;
}

这篇关于KMP算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！