目錄

• @description@
• @solution@
• @accepted code@
• @details@

---

@description@

給定一個長度為 n 的字符串 S，令 Ti 表示它從第 i 個字符開始的后綴。求：
\[\sum_{1\le i < j \le n}((len(Ti) -lcp(Ti, Tj)+(len(Tj)-lcp(Ti, Tj))\]
其中 lcp 是最長公共前綴。

input
一個長度為 n 的字符串S。2 <= n <= 500000，S由小寫英文字母組成。
output
一個整數(shù)，表示所求值。

sample input
cacao
sample output
54

@solution@

那個式子我們可以分兩部分求解：len 和 lcp。

len 部分：每一個后綴的 len 都會統(tǒng)計(jì) n-1 次。所以它對答案的貢獻(xiàn)為 \((1+2+...+n)*(n-1)\)。把等差數(shù)列的求和公式代進(jìn)去：\(\frac{(n-1)*n*(n+1)}{2}\)

lcp 部分：我們把原串翻轉(zhuǎn)，則原串中的后綴對應(yīng)新串中的前綴，我們要求解原串中的最長公共前綴就是新串中的最長公共后綴。
一個結(jié)點(diǎn)的 fa 所表示的結(jié)點(diǎn)一定是這個結(jié)點(diǎn)的后綴。所以我們最長公共后綴所表示的結(jié)點(diǎn)一定是該結(jié)點(diǎn)的某個祖先。
那么兩個結(jié)點(diǎn)的 lca 就能表示它們的最長公共后綴。因此我們作一個簡單的樹形 dp 統(tǒng)計(jì)有多少對點(diǎn)以根為 lca 即可。

實(shí)際上，后綴自動機(jī)在翻轉(zhuǎn)的串上建出來的 parent 樹，就是原串中的后綴樹。

所以后綴樹完完全全沒什么用啊喂。

@accepted code@

#include<vector> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int MAXN = 500000; vector<int>G[2*MAXN + 5]; struct sam{sam *ch[26], *fa; int mx;int tag; }pl[2*MAXN + 5], *root, *tcnt, *lst; void init() {root = tcnt = lst = &pl[0]; } sam *newnode(int x) {tcnt++; tcnt->tag = x;return tcnt; } void clone(sam *x, sam *y) {for(int i=0;i<26;i++)x->ch[i] = y->ch[i];x->fa = y->fa; } void sam_extend(int x) {sam *cur = newnode(1), *p = lst;cur->mx = lst->mx + 1; lst = cur;while( p && !p->ch[x] )p->ch[x] = cur, p = p->fa;if( !p )cur->fa = root;else {sam *q = p->ch[x];if( p->mx + 1 == q->mx )cur->fa = q;else {sam *nq = newnode(0);nq->mx = p->mx + 1;clone(nq, q);q->fa = cur->fa = nq;while( p && p->ch[x] == q )p->ch[x] = nq, p = p->fa;}} } int siz[2*MAXN + 5]; char s[MAXN + 5]; ll ans; void dfs(int rt) {siz[rt] = pl[rt].tag;for(int i=0;i<G[rt].size();i++) {int to = G[rt][i]; dfs(to);ans -= 2LL*siz[rt]*siz[to]*pl[rt].mx;siz[rt] += siz[to];} } int main() {init(); scanf("%s", s);int lens = strlen(s);ans = 1LL*(lens-1)*lens*(lens+1)/2;for(int i=lens-1;i>=0;i--)sam_extend(s[i] - 'a');for(int i=1;i<=tcnt-pl;i++) {G[pl[i].fa-pl].push_back(i);} dfs(0);printf("%lld\n", ans); }

@details@

所以真的想問問大家，后綴樹既然可以通過后綴自動機(jī)構(gòu)造出來，時間復(fù)雜度空間復(fù)雜度也不會更優(yōu)秀（因?yàn)槟悴豢赡艹^線性復(fù)雜度嘛）。

那么后綴樹到底用處在哪里？

轉(zhuǎn)載于:https://www.cnblogs.com/Tiw-Air-OAO/p/10256459.html

總結(jié)

以上是生活随笔為你收集整理的@bzoj - 3238@ [Ahoi2013]差异的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。