KMP学习记

时更。

关于前缀

一个在\(kmp\,\)中较重要的思想。

定义：

一个长度为\(n\,\)的字符串，它的前缀为$$s_1,s_1s_2,···,s_1s_2 ······s_n $$

后缀同理。

真前/后缀即去掉原字符串其他的前缀。

对于一个字符串，它的前缀函数\(\pi [i]\)为\(s_1···s_i\,\)中最长的相等的真前缀和真后缀的长度。

例abcabd（下标从1开始）

\(\pi[1]=0\)；

\(\pi[2]=0\)；

\(\pi[3]=0\)；

\(\pi[4]=1\,\)，a与a；

\(\pi[5]=2\,\)，ab与ab；

\(\pi[6]=0\)。

求解：

暴力做法，复杂度\(O(n^3)\):

for(int i=2;i<=len;i++)
{
	for(int j=i;j>=1;j--)
	{
		if(s.substr(0,j)==s.substr(i-j+1,j))
		{
			pi[i]=j;
			break;
		}
	}
}

KMP板子

题链

思路

KMP的精髓在于，对于每次失配之后，我们不会从头重新开始枚举，而是根据我们已知的数据，从某个特定的位置开始匹配。

而对于模式串的每一位，都有唯一的特定变化位置，这个在失配之后的特定变化位置可以帮助我们利用已有的数据不用从头匹配，从而节约时间。

具体例子可以自己手搓一个。

两个关键点：

1.我们的失配数组应当建立在模式串意义下，而不是文本串意义下。因为显然模式串要更加灵活，在失配后换位时，可以更灵活简便地处理。

2.移位法则：在模式串\(s\)中，对于每一位\(si\) ,它的\(kmp\)数组应当是记录一个位置 \(j\)，\(j \leq i\)并且满足\(s_i=s_j\)，并且在\(j!=1\)时满足\(s_1\)至\(s_{j-1}\)分别与\(s_{i-j+1}\)~\(s_{i-1}\)按位相等。

代码

const int Ratio=0;
const int N=1000005;
char a[N],b[N];
int lena,lenb,kmp[N];
namespace Acheron
{
	void Akmpprepare()
	{//kmp-即失配回跳到哪个位置的数组-初始化 
		int j=0;
		fo(i,2,lenb)
		{
			while(j&&b[i]!=b[j+1])//模式串自配 判0：回跳到头 
				j=kmp[j];
			if(b[j+1]==b[i])
				j++; 
			kmp[i]=j;
		}
	}
	void Akmpwork()
	{
		int j=0;
		fo(i,1,lena)
		{
			while(j>0&&b[j+1]!=a[i])//失配回跳 
				j=kmp[j];
			if(b[j+1]==a[i])//匹配成功：对应模式串位置+1 
				j++;
			if(j==lenb)
			{
				printf("%d\n",i-lenb+1);
				j=kmp[j];
			}
		}
	}
	void Aput()
	{
		fo(i,1,lenb)
			qkg(kmp[i]);
	}
}
int main()
{
	scanf("%s%s",a+1,b+1);
	lena=strlen(a+1),lenb=strlen(b+1);
	Acheron::Akmpprepare();
	Acheron::Akmpwork();
	Acheron::Aput();
	return Ratio;
}