萌新求助奇怪写法KMP
查看原帖
萌新求助奇怪写法KMP
227728
冰糖鸽子「僕は…」楼主2021/8/16 14:09

RT,WA 12pts,边KMP边模拟栈。

似乎我这种写法不多,所以可能有问题?

觉得大概率是 while 那一行的细节问题wq

#include <bits/stdc++.h>
using namespace std;
#define M 1000005
string s,t;
int sl,tl,j,n,fal[M],now;
char c[M];
int main()
{
	cin>>s>>t,sl=s.length(),tl=t.length(),n=sl+tl+1; t+="|"+s;
	for(int ij=0;ij<n;ij++)
	{
		now++,j=fal[now-1]; while(j>0&&t[ij]!=c[j+1]) j=fal[j-1]; fal[now]=j+(t[ij]==c[j+1]?1:0),c[now]=t[ij];
		if(fal[now]==tl) now-=tl;
	}
	for(int i=tl+2;i<=now;i++) cout<<c[i];
	return 0;
}
2021/8/16 14:09
加载中...