Java教程

kmp算法

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

kmp算法

#include <iostream>

using namespace std;

const int N = 10010,M = 100010;


int n,m;
char p[N],s[M];
int ne[N],nextval[N];

int main()
{
	cin>>n>>p+1>>m>>s+1;

	//求next的过程
	for(int i = 2,j = 0;i<=n;i++)
    {
        while(j&&p[i]!=p[j+1])
            j = ne[j];
        if(p[i]==p[j+1])
            j++;
        ne[i] = j;
    }

	//kmp匹配过程
	for(int i=1,j = 0;i<=m;i++)
    {
        while(j && s[i]!=p[j+1])
            j = ne[j];
        if(s[i] == p[j+1])
            j++;
        if(j == n)
        {
            printf("%d ",i - n +1);
            j = ne[j];
        }
    }
	return 0;
}

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