在 P5546 过了,但是本题 WA,求调
查看原帖
在 P5546 过了,但是本题 WA,求调
681036
OldDriverTree楼主2024/12/12 19:48

rt,不知道咋回事把求 res 那里改为 dfs\text{dfs} 就过了,神秘

//when you use vector or deque,pay attention to the size of it.
//by OldDirverTree
#include<bits/stdc++.h>
//#include<atcoder/all>
#define P pair<int,int>
#define int long long
#define mid (l+r>>1)
using namespace std;
//using namespace atcoder;
const int N=2e5;
int ans[N],res[N];
int tot=1,cur=1;
char s[N];

struct node {
	int len,fa;
	int son[26];
}T[N];

struct custom_hash
{
	static uint64_t splitmix64(uint64_t x) {
		x+=0x9e3779b97f4a7c15;
		x=(x^(x>>30) )*0xbf58476d1ce4e5b9;
		x=(x^(x>>27) )*0x94d049bb133111eb;
		return x^(x>>31);
	}
	size_t operator() (uint64_t x) const {
		static const uint64_t FIXED_RANDOM=chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x+FIXED_RANDOM);
	}
};
int read() {
	int x=0; bool f=true; char c=0;
	while (!isdigit(c) ) f&=(c!='-'),c=getchar();
	while (isdigit(c) ) x=(x<<3)+(x<<1)+(c&15),c=getchar();
	return f?x:-x;
}
void extend(int c) {
	int p=cur,np=cur=++tot; T[np].len=T[p].len+1;
	for (;p&&!T[p].son[c];p=T[p].fa) T[p].son[c]=np;
	if (!p) return T[np].fa=1,void(); int q=T[p].son[c];
	if (T[q].len==T[p].len+1) return T[np].fa=q,void();
	int nq=++tot; T[nq]=T[q],T[nq].len=T[p].len+1,T[np].fa=T[q].fa=nq;
	for (;T[p].son[c]==q;p=T[p].fa) T[p].son[c]=nq;
}
main()
{
	scanf("%s",s);
	for (int i=0;s[i];i++) extend(s[i]-'a');
	for (int i=1;i<=tot;i++) ans[i]=T[i].len;
	while (~scanf("%s",s) )
	{
		memset(res,0,sizeof res);
		for (int i=0,now=1,len=0;s[i];i++) {
			while (now^1&&!T[now].son[s[i]-'a']) now=T[now].fa,len=T[now].len;
			if (T[now].son[s[i]-'a']) now=T[now].son[s[i]-'a'],len++; res[now]=max(res[now],len);
		}
		for (int i=tot;i;i--)
		ans[i]=min(ans[i],res[i]),
		res[T[i].fa]=max(res[T[i].fa],res[i]);
	}
	int Yorushika=0;
	for (int i=1;i<=tot;i++)
	Yorushika=max(Yorushika,ans[i]);
	return !printf("%lld",Yorushika);
}
2024/12/12 19:48
加载中...