看了半天也不知道自己的错在哪里,把错误测试点下载下来运行也可以过
查看原帖
看了半天也不知道自己的错在哪里,把错误测试点下载下来运行也可以过
891817
Haiiao楼主2023/11/4 14:35
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
char s1[N],s2[N];
int Next[N];
int l1,l2;

void getNext(char s[])
{
	Next[0]=0;
	int k=0,j=1;
	while(j<l2)
	{
		if(k==0&&s[j]!=s[k])
		{
			j++;
		} 
		else if(s[j]==s[k])
		{
			Next[j]=k+1;
			k++; 
			j++;
		}
		else
			k=0;
	}
} 


void kmp(char s1[],char s2[])
{
	int i=0,j=0;
	getNext(s2);
	while(i<l1)
	{
		if(s1[i]==s2[j])
		{
			i++;
			j++;
		}
		else if(j==0)
			i++;
		else
			j=Next[j-1];
		if(j==l2)
		{
			printf("%d\n",i-j+1);
			i=i-j+1;
			j=0;
		}
	}
	for(int i=0;i<l2;i++)
		cout<<Next[i]<<" ";
	
}

int main()
{
	cin>>s1>>s2; 
	for(l1=0;s1[l1]!='\0';){l1++;}
	for(l2=0;s2[l2]!='\0';l2++){}
	cout<<l1<<endl;
	kmp(s1,s2);
	return 0;
} 
2023/11/4 14:35
加载中...