【洛谷 P3975】 [TJOI2015]弦论（后缀自动机）

桃扇骨 2021-12-21 06:39 164阅读 0赞

[题目链接][Link 1]  
建出后缀自动机。  
T=0，每个子串算一次，否则每个子串算该子串的\\(endpos\\)集合大小次。  
用\\(f\[i\]\\)表示结点\\(i\\)表示的\\(endpos\\)集合大小，则\\(f\[i\]\\)为其parent tree的子树的\\(f\\)之和(T=0时，f\[i\]均为1)。  
用\\(g\[i\]\\)表示从结点\\(i\\)出发的子串个数，则\\(g\[i\]\\)为\\(f\[i\]\\)加上结点\\(i\\)所有出边的\\(g\[v\]\\)之和。  
类似平衡树跑第\\(k\\)小。

#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #define O(x) cout << #x << "=" << x << endl; using namespace std; const int MAXN = 1000010; struct SAM{ int ch[26]; int len, fa; }sam[MAXN << 1]; int las = 1, cnt = 1, f[MAXN << 1], g[MAXN << 1]; struct Edge{ int next, to; }e[MAXN << 1]; int head[MAXN << 1], num; inline void Add(int from, int to){ e[++num].to = to; e[num].next = head[from]; head[from] = num; } inline void add(int c){ int p = las; int np = las = ++cnt; sam[np].len = sam[p].len + 1; f[cnt] = 1; for(; p && !sam[p].ch[c]; p = sam[p].fa) sam[p].ch[c] = np; if(!p) sam[np].fa = 1; else{ int q = sam[p].ch[c]; if(sam[q].len == sam[p].len + 1) sam[np].fa = q; else{ int nq = ++cnt; sam[nq] = sam[q]; sam[nq].len = sam[p].len + 1; sam[q].fa = sam[np].fa = nq; for(; p && sam[p].ch[c] == q; p = sam[p].fa) sam[p].ch[c] = nq; } } } char a[MAXN]; int t, k; void dfs(int u){ for(int i = head[u]; i; i = e[i].next){ dfs(e[i].to); f[u] += f[e[i].to]; } } void Dfs(int u){ g[u] = f[u]; for(int i = 0; i < 26; ++i) if(sam[u].ch[i]){ if(!g[sam[u].ch[i]]) Dfs(sam[u].ch[i]); g[u] += g[sam[u].ch[i]]; } } void DFS(int u, int res){ if(res <= f[u]) return; res -= f[u]; for(int i = 0; i < 26; ++i) if(sam[u].ch[i]) if(g[sam[u].ch[i]] >= res){ putchar(i + 'a'); DFS(sam[u].ch[i], res); return; } else res -= g[sam[u].ch[i]]; printf("-1\n"); } int main(){ scanf("%s", a + 1); scanf("%d%d", &t, &k); int len = strlen(a + 1); for(int i = 1; i <= len; ++i) add(a[i] - 'a'); for(int i = 2; i <= cnt; ++i) Add(sam[i].fa, i); if(t) dfs(1); else for(int i = 2; i <= cnt; ++i) f[i] = 1; f[1] = 0; Dfs(1); DFS(1, k); return 0; }

转载于:https://www.cnblogs.com/Qihoo360/p/10985965.html

[Link 1]: https://www.luogu.org/problemnew/show/P3975