kmp算法

开始了我的博客，这里的第一篇就让我来整理下kmp的简单知识吧！

用法：

kmp算法（字符串匹配算法）可以用来从一个字符串中去找另一个子字符串的存在的位置及循环次数。
eg:从字符串”AAABA”中寻找”BA”是否存在，存在的初始位置及循环次数。
一开始我未了解kmp算法到底用来干什么的时候，对用法的解释有了误解，后来就想不通都为什么要那么处理，不过一道板子题下来就可以解决啦！

说明

在解决从主串中寻找子串的问题中，我们最容易想到的就是一个个去找，但是如果两个字符串的长度稍微一大的话，那在问题中就会超时，所以要来get这个kmp算法。

寻找最长的相同前后缀

最长的前缀是指最后一个字符前的所有字符，最长的后缀指第一个字符以外的所有字符。

举例：字符串”AABABAAA”

子字符串	最长相同前后缀
A	0
AA	1
AAB	0
AABA	1
AABAB	0
AABABA	1
AABABAA	2
AABABAAA	2

把这个字符串的最短前后缀设置为next数组
一般不把最后一个最长相等前后缀的值放入next数组中，next数组的下标从0 开始，而对应的第一个字符即所对应的值我们一般设置为-1
习惯将所有的往后移一位，将第一位设为-1

0	1	2	3	4	5	6	7
A	A	B	A	B	A	A	A
-1	0	1	0	1	0	1	2

这样我们就找到了next数组的值。
寻找next数组的代码如下：

void search_next()//n为字符串的长度，p为字符串，next为相同前后缀表
{
	next[0]=-1;
	int j=-1;
	for(int i=1;i<=n-1;i++)
	{
		while(j>-1&&p[j+1]!=p[i])//注意j要大于-1，不然数组下标会越界
		{
			j=next[j];//当不相等时，回溯，直到回溯到第一个字符
		}
		if(p[j+1]==p[i])
		j++;
		next[i]=j;
	}
}

kmp算法运用

在对next数组理解以后，你再用next数组de值运用进kmp的搜索中，你会发现搜索比以前的方法会快一些。

如：在字符串”aaaaab”中去查找”aab”,用以前的方法显然麻烦多了，用kmp演示
P: aaaaab
Q： aab 匹配到第三个时，你发现不一样，照以前的方法，字符串P一般会回到首位，Q会从第二个开始和P的首位比较，而现在先求出next数组，再用kmp，会发现是直接将”aab”整体的向后移一位，这样就减少了时间。

把kmp的代码贴在下面，对着代码应该会理解：

void kmp() //数组p为要查找的字符串，而s为主串，next数组用上面的方法即可求出
{
	int j=-1;
	for(int i=0;i<m;i++)
	{
		while(j>-1&&p[j+1]!=s[i])//j也同样要大于-1
		j=next[j];
		if(p[j+1]==s[i])
		j++;
		if(j==n-1)
		{
			printf("%d ",i-j);//求出匹配好的字符串的匹配起始位置
			j=next[j];
		}
	}
}

kmp算法板子题

AcWing 831

全部代码如下：

#include<stdio.h>
#include<string.h>
int n,m;
char p[100005],s[1000005];
int next[100005];

void search_next()
{
	next[0]=-1;
	int j=-1;
	for(int i=1;i<=n-1;i++)
	{
		while(j>-1&&p[j+1]!=p[i])
		{
			j=next[j];
		}
		if(p[j+1]==p[i])
		j++;
		next[i]=j;
	}
}
void kmp()
{
	int j=-1;
	for(int i=0;i<m;i++)
	{
		while(j>-1&&p[j+1]!=s[i])
		j=next[j];
		if(p[j+1]==s[i])
		j++;
		if(j==n-1)
		{
			printf("%d ",i-j);
			j=next[j];
		}
	}
}
int main()
{
	scanf("%d",&n);
	scanf("%s",p);
	scanf("%d",&m);
	scanf("%s",s);
	search_next();
	kmp();
	return 0;
}