【暂咕咕咕】SuffixTree

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
typedef long long ll;
char s[MAXN];
int n,siz[MAXN<<1];
ll ans=0;
const int inf=1e8;
struct SuffixTree{
	int link[MAXN<<1],len[MAXN<<1],start[MAXN<<1],s[MAXN<<1];
	int n,tail,now,rem,ch[MAXN<<1][27];
	SuffixTree(){tail=1,n=0,rem=0,now=1,len[0]=inf;}
	int newnode(int st,int le){
		link[++tail]=1;start[tail]=st;len[tail]=le;return tail;
		/*build new node
		link->1,start=st(have been known)
		len->le have been known
		tail is the new number*/
	}
	void Extend(int x){
		s[++n]=x;rem++;
		/*add len(n),add rem
		n->all strings‘ number
        rem->now length(not the waited suffixstrings
        suffixstrings is showed by "rem" & "now"
        start[u]&len[u]:
        is meaning of u‘s father is s[start[u]->start[u]+len[u]-1]*/
		for(int last=1;rem;){
			while(rem>len[ch[now][s[n-rem+1]]])
				rem-=len[now=ch[now][s[n-rem+1]]];
			/*
			find the edge which the head is s[n-rem+1]
			because that len(rem) may bigger than this edge‘s len
			so we should del it‘s len and jump to the next
			this is the setp2. 
			*/
			int &v=ch[now][s[n-rem+1]];int c=s[start[v]+rem-1];
			/*
			v->the edge‘s last point
			c->this edge‘s last character
			*/
			if(!v||x==c){
				link[last]=now;last=now;
				if(!v)v=newnode(n,inf);
				/*
				 if there is no edge which is follow the rule
				 or,2 step is failed
				 then we should add the "suffix link"->link[last]=now,last=now
				*/
				else break;
				/* if we find this edge is being,also
				   the last character have been there
				   it‘s meaning that we needn‘t to add now‘s character
				   so,we should break.
				*/
			} 
			else{
				// if the last character is not being
				int u=newnode(start[v],rem-1);
				// build a new node,and split this edge
				ch[u][c]=v;ch[u][x]=newnode(n,inf);
				/*
				u->have two points:one is v->inherit the before
				and the other one is x:insert x.
				*/
				start[v]+=rem-1;len[v]-=rem-1;
				/*
				also,because we split this road
				v‘s start and len should be updated
				start+=rem-1,also the len[v] should cut rem-1
				*/
				link[last]=v=u;last=u;
				//build lead to update the suffix link.
			}
			if(now==1)rem--;
			/*
			root is 1
			if now=1,rem should be less
			*/
			else now=link[now];
			/*
			else,in order to add the next character,we should jump to the now‘s suffix link.
			the meaning of suffix link is making find the next right edge and updating it more convenient and faster.
			*/
		}
	}
}sft;
int dfs(int u,int dep){
	if(dep>=inf)return 1;
	siz[u]=0;
	for(int i=0;i<=26;++i){
		if(sft.ch[u][i]){
			/*
			if we can jump this edge 
			then,we continue to dfs and update the siz
			*/
			int d=dfs(sft.ch[u][i],dep+sft.len[sft.ch[u][i]]);
			siz[u]+=d; 
		}
	}
	if(siz[u]>=2)ans=max(ans,1LL*siz[u]*dep);//the problem‘s querying
	return siz[u];
}
int main(){
	scanf("%s",s+1);
	int n=strlen(s+1);
	for(int i=1;i<=n;++i)s[i]-=‘a‘,sft.Extend(s[i]);//Extend the string
	sft.Extend(26);//End character
	dfs(1,0);//add up the answer
	printf("%lld\n",ans);
}

\(\text{The code has explained by English.And the explaining will be updated after the High school entrance examination}\)

【暂咕咕咕】SuffixTree

原文：https://www.cnblogs.com/h-lka/p/13191105.html