略解 kmp

LittleN / 2023-08-11 / 原文

我见过kmp的两种写法：

const int N=1e6+5;
char s[N],t[N];
int ls,lt,nxt[N];
int main()
{
    cin>>s>>t;
    ls = strlen(s); lt = strlen(t);
	for(int i=1,j=0; i<lt; i++)
	{
		while(j && t[i] != t[j]) j = nxt[j];
		if(t[j] == t[i]) j++;
		nxt[i+1] = j;
	}
	for(int i=0,j=0; i<ls; i++)
	{
		while(j && t[j] != s[i]) j = nxt[j];
		if(t[j] == s[i]) j++;
		if(j == lt)
		{
			write(i-lt+2);pc('\n');
			j = nxt[j];
		}
	}
	for(int i=1;i<=lt;i++)
		write(nxt[i]), pc(' ');
    return 0;
}

const int N=1e6+5;
char s[N],t[N];
int ls,lt,nxt[N];
int main()
{
    cin>>s>>t;
    ls = strlen(s); lt = strlen(t);
	nxt[0] = -1;
	for(int i=0, j=-1; i<lt;)
	{
		if(j==-1 || t[i] == t[j])
		{
			i++; j++;
			nxt[i] = j;
		}
		else j = nxt[j];
	}
	for(int i=0,j=0; i<ls;)
	{
		if(j==-1 || s[i] == t[j]) i++, j++;
		else j = nxt[j];
		if(j == lt)
		{
			write(i-lt+1);pc('\n');
			j = nxt[j];
		}
	}
	for(int i=1;i<=lt;i++)
		write(nxt[i]), pc(' ');
    return 0;
}

（代码是 lg kmp 板子的代码）
nxt[i]数组的含义是在第 1 ~ i-1 位中前缀与后缀相同的部分最长是多长
当我们模式串和文本串这一位不相同的时候，就要跳这一位的nxt
跳到另一个有一部分匹配的地方，然后两个串接着匹配
现在在后缀的后一个字符，不相同了，就跳去前缀（前缀与后缀相同），可以省去一些时间
来看求nxt的代码：

nxt[0] = -1;
for(int i=0, j=-1; i<lt;)
{
	if(j==-1 || t[i] == t[j])//当前这一位相同或者还未匹配，一直往后走，走到第一个不同的地方
	{
		i++; j++;
		nxt[i] = j;//根据含义
	}
	else j = nxt[j];//否则就跳 nxt（不同当然得跳走啦）
}

另一份也是同理，反过来而已：

for(int i=1,j=0; i<lt; i++)
{
	while(j && t[i] != t[j]) j = nxt[j];//一直跳 nxt，跳到相同或者不能跳为止
	if(t[j] == t[i]) j++;//当前位置相同，再往后走一位
	nxt[i+1] = j;//根据含义（+1是因为下标从零开始）
}

有人说求nxt的过程是模式串自己和自己匹配，我觉得挺形象（？）
再来看求答案：

for(int i=0,j=0; i<ls;)
{
	if(j==-1 || s[i] == t[j]) i++, j++;//当前位匹配，往后走
	else j = nxt[j];//不匹配，跳 nxt
	if(j == lt)//匹配到头了
	{
		write(i-lt+1);pc('\n');
		j = nxt[j];//跳 nxt（因为没地方可以匹配了）
	}
}

同上：

for(int i=0,j=0; i<ls; i++)
{
	while(j && t[j] != s[i]) j = nxt[j];//一直跳 nxt，跳到相同或者不能跳为止
	if(t[j] == s[i]) j++;//匹配成功，往后走一位
	if(j == lt)//匹配到头
	{
		write(i-lt+2);pc('\n');
		j = nxt[j];//跳 nxt
	}
}

另外推荐一篇讲kmp的博客，我是看了他才懂的（orz）