字符串匹配——KMP算法

给定两个字符串s1和s2，询问s2在s1中出现的位置（定义为出现时的第一个字符在s1中的位置）

暴力枚举

看到字符串匹配(如果你还不会KMP/Hash的话)，八成是要用暴力枚举的方法（可是这样极其容易被卡掉）因此三位神犇发明了KMP算法

顺便%一下dalao

D. E. Knuth 、J.H. Morris and V.R.Pratt

next数组

KMP算法的核心操作

为了方便，我们将s1定义为主串，s2定义为模式串

可以从左到右一位一位的匹配，失配了就从头再来（这是暴力枚举）

所以我们可以想更优的方法，利用已经匹配的部分，从而只移动模式串，让主串保持不变，可以用指针j表示模式串匹配到了哪一位

举个栗子

ABCABCDEFG
ABCABB

发现匹配到第六位时失配力，此时j在B也就是第六位

可以移动一下

ABCABCDEFG
   ABCABB

此时j在C的位置（第三位）力

可以看出，每次移动后，假如移动j到了k,则字符串前k-1位==j之前的k-1位

所以我们可以用next数组来记录对于每一个j的k的位置，即最长公共前后缀de长度

而对于第1位/第2位，其最长公共前后缀的长度始终为1

即next[0]=1,next[1]=1;

预处理&匹配

上文介绍了next数组以及指针j如何移动

那么怎么预处理next数组呢？

其实很简单

让模式串与自己匹配就好啦

	for(int i=2;i<=len_b;i++)
	{
		while(j && b[j+1]!=b[i])
		{
			j=kmp[j];
		}
		
		if(b[j+1]==b[i])
		{
			j++;
		}
		
		kmp[i]=j;
	}

然后就是主串与模式串之间的匹配

	for(int i=1;i<=len_a;i++)
	{
		while(j && b[j+1]!=a[i])
		{
			j=kmp[j];
		}
		
		if(b[j+1]==a[i])
		{
			j++;
		}
		
		if(j==len_b)
		{
			cout<<i-j+1<<endl;
			j=kmp[j];
		}
	}

完整の板子

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>

using namespace std;

const int maxn=1e6+5;

int kmp[maxn],j;

int len_a,len_b;

char a[maxn],b[maxn];

int main()
{
	cin>>a+1;
	cin>>b+1;
	
	len_a=strlen(a+1);
	len_b=strlen(b+1);
	
	for(int i=2;i<=len_b;i++)
	{
		while(j && b[j+1]!=b[i])
		{
			j=kmp[j];
		}
		
		if(b[j+1]==b[i])
		{
			j++;
		}
		
		kmp[i]=j;
	}
	
	j=0;
	
	for(int i=1;i<=len_a;i++)
	{
		while(j && b[j+1]!=a[i])
		{
			j=kmp[j];
		}
		
		if(b[j+1]==a[i])
		{
			j++;
		}
		
		if(j==len_b)
		{
			cout<<i-j+1<<endl;
			j=kmp[j];
		}
	}
	
	for(int i=1;i<=len_b;i++)
	{
		cout<<kmp[i]<<" ";
	}
	
	return 0;
}

無限はゼロに近いが、ゼロではない可能性がある