后缀自动机(SAM)模板代码
学习一周终于看懂模板
放一份代码
#include<bits/stdc++.h>
#define pb push_back
using namespace std;class SAM{
public:static const int N=2e6+10; // 最大节点数，字符串长1e6，SAM最多2e6节点struct node{int t[26],f,len,cnt; // t:转移边 f:后缀链接 len:最长长度 cnt:出现次数}a[N];int idx=1,lst=1; // idx:节点总数 lst:上次插入节点vector<int> g[N]; // parent树邻接表void add(int c){int p=lst,np=++idx; lst=np; // 创建新节点，更新lasta[np].len=a[p].len+1; // 新节点长度+1a[np].cnt=1; // 主链节点出现次数初始为1memset(a[np].t,0,sizeof a[np].t); // 清空转移数组for(;p && !a[p].t[c];p=a[p].f) a[p].t[c]=np; // 将没有c转移的节点指向npif(!p) a[np].f=1; // case1: 跳到根，后缀链接指向1else{int v=a[p].t[c];if(a[v].len==a[p].len+1) a[np].f=v; // case2: 可直接连else{int nv=++idx; // case3: 需要克隆节点memcpy(a[nv].t,a[v].t,sizeof a[v].t); // 复制转移边a[nv].len=a[p].len+1; // 克隆节点长度设为p.len+1a[nv].f=a[v].f; // 克隆节点后缀链接指向v的后缀链接a[nv].cnt=0; // 克隆节点不是主链，出现次数为0for(;p && a[p].t[c]==v;p=a[p].f) a[p].t[c]=nv; // 将指向v的转移改为指向nva[v].f=a[np].f=nv; // 更新v和np的后缀链接}}}void dfs(int u){for(int v:g[u]) dfs(v),a[u].cnt+=a[v].cnt; // 递归子节点并累加出现次数}long long query(){for(int i=2;i<=idx;i++) g[a[i].f].pb(i); // 建parent树，将节点挂到父节点下dfs(1); // 从根开始DFS累加cntlong long ret=0;for(int i=1;i<=idx;i++) if(a[i].cnt>1) ret=max(ret,1ll*a[i].cnt*a[i].len);return ret;}
}sam;string s;int main(){cin.tie(0)->sync_with_stdio(0);cin>>s;for(char c:s) sam.add(c-'a');cout<<sam.query()<<'\n';return 0;
}/*** 解题思路：* 1. SAM每个节点代表endpos相同的子串集合，len[i]是最长长度，cnt是出现次数* 2. 插入字符时，主链节点cnt=1，克隆节点cnt=0* 3. 构建parent树(后缀链接树)，DFS从叶子向上累加cnt* 4. 最终每个节点的cnt就是它代表的所有子串的出现次数* 5. 遍历所有节点，若cnt>1则更新ans = max(ans, cnt * len[i])* * 时间复杂度O(n)，空间复杂度O(n*|Σ|)*/
