蒟蒻10分求助!!!
  • 板块学术版
  • 楼主fanke
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/4/15 11:18
  • 上次更新2023/10/23 18:27:05
查看原帖
蒟蒻10分求助!!!
547120
fanke楼主2023/4/15 11:18

刚学后缀自动机,不熟练,有没有大佬帮帮我啊

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n , tot , lst;
ll ans = 0;
struct point{
	int len , fa;
	ll size;
	int son[26];
	point()
	{
		len = fa = 0;
		size =  0ll;
		memset(son , 0 , sizeof(son));
	}
}d[1000001];
char s[1000001];
int tmp[1000001] , tp[2000001];
void sam(int now)
{
	int p = lst;
	int np = ++ tot;
	lst = np;
	d[np].size = 1;
	d[np].len = d[p].len + 1;
	for(; p && !d[p].son[now] ; p = d[p].fa)
		d[p].son[now] = np;
	if(!p)
		d[np].fa = 1;
	else
	{
		int q = d[p].son[now];
		if(d[q].len == d[q].len + 1)
			d[np].fa = q;
		else 
		{
			int nq = ++ tot;
			d[nq] = d[q];
			d[nq].size = 0;
			d[nq].len = d[p].len + 1;
			d[q].fa = nq;
			d[np].fa = nq;
			for(; p && d[p].son[now] == q ; p = d[p].fa)
				d[p].son[now] = nq;	
		}	
	} 
}
void get_tp()
{
	for(int i = 0 ; i <= n ; i ++)
		tmp[i] = 0;
	for(int i = 1 ; i <= tot ; i ++)
		tmp[d[i].len] ++;
	for(int i = 1 ; i <= n ; i ++)
		tmp[i] += tmp[i - 1];
	for(int i = 1 ; i<= tot ; i ++)
		tp[tmp[d[i].len] --] = i; 
}
void dp()
{
	for(int i = tot ; i >= 1 ; i --)
	{
		int now = tp[i];
		d[d[now].fa].size += d[now].size;	
	} 
	for(int i = 1 ; i <= tot ;i ++)
		if(d[i].size > 1)
			ans = max(ans , d[i].size * d[i].len); 
}
int main()
{
	scanf("%s" , s + 1);
	n = strlen(s + 1);
	tot = lst = 1;
	for(int i = 1 ;  i <= n ;i ++)
		sam(s[i] - 'a');
	get_tp();
	dp();
	printf("%lld\n" ,ans);
    return 0;
}

2023/4/15 11:18
加载中...