社区讨论

我是小白,虽然不是女生,但是刚学OI,求大佬帮助!!!

P3375【模板】KMP参与者 11已保存回复 12

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
12 条
当前快照
1 份
快照标识符
@mi7we31u
此快照首次捕获于
2025/11/21 04:42
4 个月前
此快照最后确认于
2025/11/21 06:33
4 个月前
查看原帖
kmp玄学错误。。。
我的码风应该不会很奇怪吧
CPP
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int next[1000005];
char text[1000005],mo[1000005];
void kmp(int n);
int main()
{
	scanf("%s%s",text,mo);
	int n=strlen(mo),m=strlen(text),j=0;
	kmp(n);
	for(int i=0;i<m;i++)
	{
		//printf("in i=%d,j=%d\n",i,j);
		while(j&&text[i]!=mo[j])
		 j=next[j];
		if(text[i]==mo[j])
		 j++;
		if(j==n)
		{
			//cout<<i-j+2<<endl;
			printf("%d\n",i-j+2);
			j=next[j-1];
		} 
	}
	for(int i=0;i<n;i++)
	 printf("%d ",next[i]);
	cout<<endl;
	return 0;
}
void kmp(int n)
{
	int j=0;
	for(int i=1;i<n;i++)
	{
		while(j&&mo[i]!=mo[j])
		 j=next[j];
		if(mo[i]==mo[j])
		 j++;
		next[i]=j;
	}
	return;
}

回复

12 条回复,欢迎继续交流。

正在加载回复...