dfs炸了求助
查看原帖
dfs炸了求助
252551
Xqbk楼主2021/12/6 22:21
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN=1111111;
const int SIG=30;
char str[MAXN];
int len[MAXN],tr[MAXN][SIG],lnk[MAXN],siz=1,lst=1;
void extend(int id)
{
	int cur=++siz;
	len[cur]=len[lst]+1;
	int u;
	for(u=lst;u&&!tr[u][id];u=lnk[u])
	{
		tr[u][id]=cur;
	}
	if(!u)lnk[cur]=1;
	else
	{
		int v=tr[u][id];
		if(len[v]==len[u]+1)lnk[cur]=v;
		else
		{
			int cc=++siz;
			len[cc]=len[u]+1;
			memcpy(tr[cc],tr[v],SIG-1);
			lnk[cc]=lnk[v];
			for(;u&&tr[u][id]==v;u=lnk[u])
			{
				tr[u][id]=cc;
			}
			lnk[cur]=lnk[v]=cc;
		}
	}
	lst=cur;
}
int num[MAXN];
int vis[MAXN];
long long ans;
void dfs(int u)
{
	if(!u)return;
	vis[u]=1;
	for(int i=0;i<26;i++)
	{
		int v=tr[u][i];
		if(!v)continue;
		if(!vis[v])
		{
			dfs(v);
		}
		num[u]+=num[v];
	}
	if(num[u]>1)
	{
		ans=max(ans,1ll*num[u]*len[u]);
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	cin>>str;
	for(int i=0;i<strlen(str);i++)
	{
		extend(str[i]-'a');
	}
	while(lst!=1)
	{
		num[lst]++;
		lst=lnk[lst];
	}
	dfs(1);
	cout<<ans<<endl;
}
2021/12/6 22:21
加载中...