萌新求助,刚学 SAM, 0 pts
查看原帖
萌新求助,刚学 SAM, 0 pts
60864
tiger2005楼主2021/1/11 17:46
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

namespace SAM{
	const int MAXN = 1000010;
	struct state{
		int len,link,next[26];
		state(){
			len=link=0;
			memset(next,0,sizeof(next));
		}
	};
	state st[MAXN<<1];
	int nn,las;
	void initSAM(){las=nn=1;}
	void expand(char c){
		c-='a';
		int curr=++nn;
		st[curr].len=st[las].len+1;
		int p=las;
		while(p!=0 && !st[p].next[(int)c]){
			st[p].next[(int)c]=curr;
			p=st[p].link;
		}
		if(p==0)	st[curr].link=1;
		else{
			int q=st[p].next[(int)c];
			if(st[q].len==st[p].len+1)
				st[curr].link=q;
			else{
				int cloned=++nn;
				st[cloned].link=st[q].link;
				for(int i=0;i<26;i++)	st[cloned].next[i]=st[q].next[i];
				st[cloned].len=st[p].len+1;
				while(p!=0 && st[p].next[(int)c]==q){
					st[p].next[(int)c]=cloned;
					p=st[p].link;
				}
				st[q].link=st[curr].link=cloned;
			}
		}
		las=curr;
	}
}
char str[1000010];

int qxx[2000010][2],tt[2000010],nn;
void ad(int x,int y){
	qxx[++nn][0]=y;
	qxx[nn][1]=tt[x];
	tt[x]=nn;
}

long long ans=0;
int dfs(int x){
	int cur=1;
	for(int i=tt[x];i;i=qxx[i][1])
		cur+=dfs(qxx[i][0]);
	if(cur!=1)
		ans=max(ans,1ll*SAM::st[x].len*cur);
	return cur;
}
int main(){
	scanf(" %s",str+1);
	SAM::initSAM();
	for(int i=1;str[i];i++)
		SAM::expand(str[i]);
	for(int i=1;i<=SAM::nn;i++)
		ad(SAM::st[i].link,i);
	dfs(1);
	printf("%lld",ans);
	return 0;
}
inp ---------
babaabbbbbbabbaabaaaaabbbaabaabaabbabaaabababaaabbbbabbbaaabbbabbaababbbabbaabaaaaabbbaabaabaabbabbaabaaabbbbabbbaaabbbaababbbbbbaaababbbbabbaabaaaaabbbaabaabaabbabbababaabaaabbbbabbbaaabbbabbbaaaababaabbbbabbaabaaaaabbbaabaabaabbabbababaaabbbbabbbaaabbbaababbbabbaabaaaaabbbaabaabaabbababbabaaabbbbabbbaaabbbabaabaaaabbbbbabbaabaaaaabbbaabaabaabbabababaabaaabbbbabbbaaabbbbbaaabbbabbabbaabbbabbaabaaaaabbbaabaabaabbabbabbaaabbbbabbbaaabbbabbaaabbababbbabbaabaaaaabbbaabaabaabbabababbaaabbbbabbbaaabbbbaabbabaaabbbabbaabaaaaabbbaabaabaabbabaabaaabbbbabbbaaabbbbabbaabaaabbbabbaabaaaaabbbaabaabaabbabababbabbbbaaabbbbabbbaaabbbbbbbabbaaabbbabbaabaaaaabbbaabaabaabbabbbbaaabbbbabbbaaabbbabaabbabbbabbaabaaaaabbbaabaabaabbabbbbaabbababaaabbbbabbbaaabbbabbabaabbbabbaabaaaaabbbaabaabaabbabaabbbaaabbbbabbbaaabbbaaabbaababbbbbabbaabaaaaabbbaabaabaabbabaaabbaaabbbbabbbaaabbbbaaaababaabbbabbaabaaaaabbbaabaabaabbabbbaaabbbbabbbaaabbbaabbbbabbaabaaaaabbbaabaabaabbabbbabbbaaabbbbabbbaaabbbbabababbaabaaababa
ans ---------
552
out ---------
1092
2021/1/11 17:46
加载中...