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

题目描述

给定一个只包含小写字母的字符串 SSS。

请你求出 SSS 的所有出现次数不为 111 的子串的出现次数乘上该子串长度的最大值。

输入格式

一行一个仅包含小写字母的字符串 SSS。

输出格式

一个整数，为所求答案。

样例 #1

样例输入 #1

abab

样例输出 #1

4

提示

对于 10%10 \%10% 的数据，∣S∣≤1000\lvert S \rvert \le 1000∣S∣≤1000。
对于 $100% $的数据，1≤∣S∣≤1061 \le \lvert S \rvert \le {10}^61≤∣S∣≤106。

后缀自动机， 需要维护3个数组ch[x][c]	存节点x转移边终点fa[x]		存节点x的链接边终点len[x]		存节点x的最长串的长度后缀链接树, 抽离图中的链接边
合法性： 子节点的最短串的最长后缀 = 父节点的最长串1、 节点x的子串长度： 最长 len[x], 最短 len[y] + 1 (y 是x节点的父节点)
2、 节点x的子串数量： len[x] - len[y] (y 是x节点的父节点)
3、 子串出现次数： cnt[x] (独立建立一颗后缀树，跑 dfs， 更新每个节点的cnt)后缀树 ： 2n - 1 个点， 3n - 4 条边
后缀链接树： 2n 个点， 2n 条边

#include 
using namespace std;
typedef long long ll;
const int N = 2e6 + 10, M = 2e6 + 10;
char s[N];
int n;
ll cnt[N], ans;
int tot = 1, np = 1;
int fa[N], ch[N][26], len[N];int tot1;
int ver[M], Next[M], head[N];void add(int x, int y)
{ver[++tot1] = y, Next[tot1] = head[x], head[x] = tot1;
}void extend(int c)
{// p回跳指针，np 新节点// q链接点，nq 新链接点int p = np; np = ++tot;				//p指向旧节点， np是新点len[np] = len[p] + 1; cnt[np] = 1;	//子串出现次数//p沿着链接边回跳，从旧节点向新点建转移边for(; p && !ch[p][c]; p = fa[p])ch[p][c] = np;//1、 如果c是新字符， 从新点向根节点建链接边if(p == 0)fa[np] = 1;else{int q = ch[p][c];	//q是链接点//2、 若链接点合法，从新点向链接点接边if(len[q] == len[p] + 1)fa[np] = q;//3、若链接边不合法， 则裂开q点，重建两类边else{int nq = ++tot;	//nq 是新建链接点len[nq] = len[p] + 1;//重建 nq, q, np 的链接边fa[nq] = fa[q]; fa[q] = nq; fa[np] = nq;// 指向q的转移边改为指向nqfor(; p && ch[p][c] == q; p = fa[p])ch[p][c] = nq;//从q发出的转移边复制给 nqmemcpy(ch[nq], ch[q], sizeof(ch[q]));}}
}void dfs(int x)
{
//	printf("x = %d\n", x);for(int i = head[x]; i; i = Next[i]){int y = ver[i];dfs(y);cnt[x] += cnt[y];}if(cnt[x] > 1)ans = max(ans, (ll)cnt[x] * len[x]);
}int main()
{scanf("%s", s + 1);n = strlen(s + 1);for(int i = 1; i <= n; ++i){extend(s[i] - 'a');}for(int i = 2; i <= tot; ++i){add(fa[i], i);}dfs(1);printf("%lld\n", ans);return 0;
}