【学习笔记】KMP算法

发布于 2019-10-04  613 次阅读


兹以为看了这个视频就能看懂

点这里

如果看不了的话。。。

抱歉了老师

对于所讲的例题

代码如下

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<stack>
#include<map>
#define N 1000010
#define INF 0x3f3f3f3f
#define pi 3.1415926535897932384626433

using namespace std;

int n;
char str[N];
int Next[N];

void get_Next()
{
	for (int i=2,j=0;i<=n;i++)
	{
		while (j>0 && str[i]!=str[j+1]) j=Next[j];
		if (str[i]==str[j+1]) j++;
		Next[i]=j;
	}
}

int main()
{
	int T=1;
	while (scanf("%d",&n),n)
	{
		scanf("%s",str+1);
		get_Next();
		printf("Test case #%d\n",T++);
		for (int i=2;i<=n;i++)
		{
			int t=i-Next[i];
			if (t!=i && i%t==0) printf("%d %d\n",i,i/t);
		}
		puts("");
	}
	return 0;
}

再来一道模板题加深理解

题目地址

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<stack>
#include<map>
#define N 1000010
#define INF 0x3f3f3f3f
#define pi 3.1415926535897932384626433

using namespace std;

int n,m;
char s1[N],s2[N];
string s;
int Next[N];

void get_Nexts2()
{
	for (int i=2,j=0;i<=m;i++)
	{
		while (j>0 && s2[i]!=s2[j+1]) j=Next[j];
		if (s2[i]==s2[j+1]) j++;
		Next[i]=j;
	}
	return;
}

void get_ans()
{
	for (int i=1,j=0;i<=n;i++)
	{
		while (j>0 && (j==m || s1[i]!=s2[j+1])) j=Next[j];
		if (s1[i]==s2[j+1]) j++;
		if (j==m) cout<<i-m+1<<endl;
	}
}

int main()
{
	cin>>s;
	n=s.length();
	for (int i=1;i<=n;i++)
		s1[i]=s[i-1];
	cin>>s;
	m=s.length();
	for (int i=1;i<=m;i++)
		s2[i]=s[i-1];
	get_Nexts2();
	get_ans();
	for (int i=1;i<=m;i++) cout<<Next[i]<<' ';
	cout<<endl;
	return 0;
}


I laid my burdens down, now I'm traveling light.
I found my freedom now, and I'm traveling light.