洛谷 P3804 【模板】后缀自动机 (SAM)

传送门
终于搞懂了这个东西，以后会多做几道后缀自动机的题的，顺便复习一下后缀数组。
这篇博客讲后缀自动机讲的很不错，推荐初学者看这篇博客学习。
后缀自动机还有很多的性质我还不是很懂，靠之后做的题来补就是了。
这道题最后的清算有两种办法，一种是重新建图dfs，比较方便，还有一种就是按长度对节点进行基数排序，结果就是par树的拓扑序列，然后倒着加。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <queue>
using namespace std;
typedef long long LL;
const int N=1e6+10;
char s[N];
struct SAM{
	char *s;
	int g[N*2][26],fa[N*2],last,tot,len[N*2],f[N*2];
	vector<int> tr[N*2];
	LL ans;
	int newnode(){++tot;memset(g[tot],0,sizeof(g[tot]));fa[tot]=len[tot]=0;return tot;}
	void add(int c){
		int p=last,np=last=newnode();
		len[np]=len[p]+1;f[np]=1;
		for(;p&&!g[p][c];p=fa[p]) g[p][c]=np;
		if(!p) fa[np]=1;
		else{
			int q=g[p][c];
			if(len[q]==len[p]+1) fa[np]=q;
			else{
				int nq=newnode();memcpy(g[nq],g[q],sizeof(g[nq]));fa[nq]=fa[q];
				len[nq]=len[p]+1;
				fa[q]=fa[np]=nq;
				for(;p&&g[p][c]==q;p=fa[p]) g[p][c]=nq;
			}
		}
	}
	void dfs(int u){
		for(int v:tr[u]) dfs(v),f[u]+=f[v];
		if(f[u]>1) ans=max(ans,1ll*f[u]*len[u]);
	}
	void init(char *_s){
		s=_s;last=newnode();
		for(int i=1;s[i]!=' ';i++) add(s[i]-'a');
		for(int i=2;i<=tot;i++) tr[fa[i]].push_back(i);
		dfs(1);
	}
}sam;


int main(){
	scanf("%s",s+1);
	sam.init(s);
	printf("%lld
",sam.ans);
	return 0;
}