资讯详情

写在前面

肝硬化太菜了发现根本不会后缀数组（SA）和后缀自动机（SAM），曾经的我非常懦弱而畏惧学习 SAM 而企图学习 SA 萌混过关，但是发现患有痴呆症的 $rAIn$ 对于 SA 的学习根本就是学一次忘一次，于是牠鼓起勇气打起精神学习了 SAM………

推歌：《炉心熔解》。

---

SAMの定义内容性质特点与其他东西的异同意义影响炼字修辞环境描写插叙倒叙比兴重章叠句一词多义古今异义

由于各种大手子都在争相认为自己是区，肝硬化显然比神犇蒻 inf 倍不止，牠需要一个比区还要微小的形容词来形容自己，于是牠钦定牠是石。

石当然讲不明白 SAM 这么深刻的事物，牠收集了一篇《深度好文》。

这个奶妈写得相当清晰易懂！！！

这里给出一个肝硬化制造的清晰好贺(bushi)好背的板子！

#define trie(x) sam[(x)]. trie
#define lnk(x) sam[(x)]. lnk
#define len(x) sam[(x)]. len
struct hhh{int trie[27], lnk, len;
}sam[_ << 1];
inline void insert(int x){int p = bfr, np = bfr = ++ cnt;len(np) = len(p) + 1;for(; p && ! trie(p)[x]; p = lnk(p)){trie(p)[x] = np;}if(! p){lnk(np) = 1;}else{int q = trie(p)[x];if(len(q) == len(p) + 1){lnk(np) = q;}else{int nw = ++ cnt;sam[nw] = sam[q];len(nw) = len(p) + 1;lnk(q) = lnk(np) = nw;for(; p && trie(p)[x] == q; p = lnk(p)){trie(p)[x] = nw;}}}return ;
}

然后大家就可以爆切 SAM 啦！（欸我到底在和谁对话………）

---

【模板】后缀自动机（SAM）

想自己总结来着但是发现用自己的语言好像说不很通顺于是图省事直接粘了上面推荐的博文的一段话………

因为在同一个等价类中，每个串出现次数相同，显然长度最长的串才可能对答案产生贡献，于是我们做树形 DP 统计出现次数再直接乘上 len 即可。

Code

#include <bits/stdc++.h>
using namespace std;
const int _ = 1000010;
int n, to[_ << 1], nxt[_ << 1], h[_ << 1], tot, ci[_ << 1], bfr = 1, cnt = 1;
long long ans;
string s;
inline void add(int x, int y){to[++ tot] = y;nxt[tot] = h[x];h[x] = tot;return ;
}
#define trie(x) sam[(x)]. trie
#define lnk(x) sam[(x)]. lnk
#define len(x) sam[(x)]. len
struct hhh{int trie[27], lnk, len;
}sam[_ << 1];
inline void insert(int x){int p = bfr, np = bfr = ++ cnt;ci[np] = 1, len(np) = len(p) + 1;for(; p && ! trie(p)[x]; p = lnk(p)){trie(p)[x] = np;}if(! p){lnk(np) = 1;}else{int q = trie(p)[x];if(len(q) == len(p) + 1){lnk(np) = q;}else{int nw = ++ cnt;sam[nw] = sam[q];len(nw) = len(p) + 1;lnk(q) = lnk(np) = nw;for(; p && trie(p)[x] == q; p = lnk(p)){trie(p)[x] = nw;}}}return ;
}
inline void dfs(int x){for(int i = h[x]; i; i = nxt[i]){int y = to[i];dfs(y);ci[x] += ci[y];}if(ci[x] > 1){ans = max(ans, 1ll * ci[x] * len(x));}return ;
}
int main(){ios :: sync_with_stdio(0), cin. tie(0), cout. tie(0);cin >> s;n = s. size();for(int i = 0; i < n; i ++){insert(s[i] - 'a');}for(int i = 2; i <= cnt; i ++){add(lnk(i), i);}dfs(1);cout << ans;return 0;
}

后面的明天写喵！