[关闭]
@ljt12138 2017-03-11T21:54:49.000000Z 字数 23045 阅读 963

后缀自动机学习笔记

算法

主要思想

后缀树和后缀数组是处理字符串的有力武器，但一个更为强大的数据结构——后缀自动机往往更加灵活。字符串S的后缀自动机被定义为一个接受S的所有后缀的有限状态自动机。一个暴力的构造方法是对于S的每个子串建立一个节点，将后缀设为接受节点。然而这样的时空复杂度都达到了。显然是不能接受的。

考虑一个字符串abaabac，当我们用b或者ab去匹配他们时，得到的匹配位置“终点”集合都为，因此和转移到达的终点集合都相等。因此可以将他们合并成一个节点。换言之，我们不再维护所有的“子串”，而去维护用子串在原字符串上匹配得到的终点集合作为自动机的状态。可以证明，这样的状态数和转移数都是的，这样构造出的自动机称为最简状态后缀自动机。

终点集合的性质

不难发现，所有的有意义终点集合构成真包含关系，即两个集合要么不相交，要么真包含。我们可以利用包含关系建立一棵树结构，我们称其为Parent树。树上的节点所对应的终点集合真包含其儿子对应的终点集合，且

那么显然也有

同一终集合内字符串长度的性质

我们发现同一终点集合内对应的字符串的长度构成一个区间，记为x对应终点集合内长度最短的字符串，反之，那么有：

也就是说：在Parent树上祖先的max比后代的min小，祖先的集合真包含后代的集合

结构

我们维护的自动机有两个逻辑结构，一个是trans(S, a)表示状态S加上字符a到达的新状态形成的DAG，一个是par(S)形成的Parent树。两个结构的性质有：

构建

构建具体方法见陈立杰的冬令营讲稿。

  1. void push(int x)
  2. {
  3.     int p = last, np = ++top; // 新建节点
  4.     maxl[np] = maxl[p]+1;
  5.     while (p && !chl[p][x]) chl[p][x] = np, p = fa[p]; // 如果还没有连边
  6.     if (!p) fa[np] = root; // 到达root
  7.     else {
  8.         int q = chl[p][x]; // 冲突节点
  9.         if (maxl[q] == maxl[p]+1) fa[np] = q; // 如果已经放满，合并状态，这时np在DAG
  10.         else {            // 中被合并至q，但Parent树中仍保存结构
  11.             int nq = new_node(q); // 建立公共祖先
  12.             maxl[nq] = maxl[p]+1;
  13.             fa[nq] = fa[q], fa[q] = nq, fa[np] = nq;
  14.             while (p && chl[p][x] == q) chl[p][x] = nq, p = fa[p]; // 换边
  15.         }
  16.     }
  17.     last = np;
  18. }

应用

USACO牛奶模式

给定一个长度为n的字符串S，和一个正整数k。求在S中出现至少k次的最长子串。

分析与解：

a. SA解法：建立height数组。考虑出现k次在height数组中的形态，由于要最大化公共子串即区间RMQ，最优解一定是长度为k的连续区间。用单调队列维护一个滑动窗口即可。最优复杂度，用DA则是。
b. SAM解法：由于在自动机中匹配位置相同的子串被收在一个状态内，一个状态的最优解即为这个状态的max。如何确定出现k次？就是。利用公式(2)预处理节点的Right，然后枚举一遍每个节点即可。由于字符集太大需要用map维护，摊还分析可知map的总操作量是的，因而总复杂度为。

SA+DA:

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int maxn = 21000;
  5. struct suffix_array {
  6.     int A[maxn], n, l, sa[maxn], rank[maxn], height[maxn], C[maxn];
  7.     struct radix_ele {
  8.         int id;
  9.         int k[2];
  10.         radix_ele(){}
  11.         radix_ele(int a, int b, int c) { id = a, k[0] = b, k[1] = c; }
  12.     } RE[maxn], RT[maxn];
  13.     void radix_sort()
  14.     {
  15.         for (int y = 1; y >= 0; y--) {
  16.             memset(C, 0, sizeof C);
  17.             for (int i = 1; i <= n; i++) C[RE[i].k[y]]++;
  18.             for (int i = 1; i < maxn; i++) C[i] += C[i-1];
  19.             for (int i = n; i >= 1; i--) RT[C[RE[i].k[y]]--] = RE[i];
  20.             for (int i = 1; i <= n; i++) RE[i] = RT[i];
  21.         }
  22.         for (int i = 1; i <= n; i++) {
  23.             rank[RE[i].id] = rank[RE[i-1].id];
  24.             if (RE[i].k[0] != RE[i-1].k[0] || RE[i].k[1] != RE[i-1].k[1])
  25.                 rank[RE[i].id]++;
  26.         }
  27.     }
  28.     void calc_sa()
  29.     {
  30.         for (int i = 1; i <= n; i++) RE[i] = radix_ele(i, A[i], 0);
  31.         radix_sort();
  32.         for (int i = 1; i < n; i <<= 1) {
  33.             for (int j = 1; j <= n; j++) RE[j] = radix_ele(j, rank[j], i+j<=n?rank[i+j]:0);
  34.             radix_sort();
  35.         }
  36.         for (int i = 1; i <= n; i++) sa[rank[i]] = i;
  37.     }
  38.     void calc_height()
  39.     {
  40.         int h = 0;
  41.         for (int i = 1; i <= n; i++) {
  42.             if (rank[i] == 1) h = 0;
  43.             else {
  44.                 int k = sa[rank[i]-1];
  45.                 if (--h < 0) h = 0;
  46.                 while (A[i+h] == A[k+h]) h++;
  47.             }
  48.             height[rank[i]] = h;
  49.         }
  50.     }
  51.     void init()
  52.     {
  53.         calc_sa();
  54.         calc_height();
  55.     }
  56. } SA;
  57. int k;
  59. struct p {
  60.     int dat, id;
  61.     p(){}
  62.     p(int a, int b) : dat(a), id(b) {}
  63. };
  64. deque<p> deq;
  66. int main()
  67. {
  68.     scanf("%d%d", &SA.n, &k);
  69.     for (int i = 1; i <= SA.n; i++)
  70.         scanf("%d", &SA.A[i]);
  71.     SA.init();
  72.     int ans = 0;
  73.     for (int i = 1; i <= SA.n; i++) {
  74.         while (!deq.empty() && i-deq.front().id+2 > k) deq.pop_front();
  75.         while (!deq.empty() && deq.back().dat > SA.height[i]) deq.pop_back();
  76.         deq.push_back(p(SA.height[i], i));
  77.         if (!deq.empty()) ans = max(ans, deq.front().dat);
  78.     }
  79.     cout << ans << endl;
  80.     return 0;
  81. }

SAM+Map:

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 20005;
  6. int stk[MAXN*2], top = 0;
  7. int rd[MAXN*2], right_siz[MAXN*2];
  9. struct SAM {
  10.     map<int, int> chl[MAXN*2];
  11.     int fa[MAXN*2], maxl[MAXN*2], root, top, last;
  12.     void init()
  13.     {
  14.         root = top = last = 1;
  15.         memset(fa, 0, sizeof fa);
  16.         memset(maxl, 0, sizeof fa);
  17.     }
  18.     void push(int x)
  19.     {
  20.         int p = last, np = ++top;
  21.         maxl[np] = maxl[last] + 1;
  22.         right_siz[np] = 1;
  23.         while (p && chl[p][x] == 0) chl[p][x] = np, p = fa[p];
  24.         if (!p) fa[np] = root;
  25.         else {
  26.             int q = chl[p][x];
  27.             if (maxl[q] == maxl[p] + 1) fa[np] = q;
  28.             else {
  29.                 int nq = ++top; maxl[nq] = maxl[p] + 1;
  30.                 chl[nq] = chl[q];
  31.                 fa[nq] = fa[q], fa[q] = fa[np] = nq;
  32.                 while (p && chl[p][x] == q) chl[p][x] = nq, p = fa[p];
  33.             }
  34.         }
  35.         last = np;
  36.     }
  37. } sam;
  39. void top_sort()
  40. {
  41.     memset(rd, 0, sizeof rd);
  42.     for (int i = 1; i <= sam.top; i++) rd[sam.fa[i]]++;
  43.     for (int i = 1; i <= sam.top; i++) if (rd[i] == 0) stk[++top] = i;
  44.     while (top) {
  45.         int tp = stk[top--]; right_siz[sam.fa[tp]] += right_siz[tp];
  46.         if (--rd[sam.fa[tp]] == 0) stk[++top] = sam.fa[tp];
  47.     }
  48. }
  50. int solve()
  51. {
  52.     int n, k;
  53.     sam.init();
  54.     scanf("%d%d", &n, &k);
  55.     for (int i = 1; i <= n; i++) {
  56.         int u; scanf("%d", &u);
  57.         sam.push(u);
  58.     }
  59.     top_sort();
  60.     int ans = 0;
  61.     for (int i = 2; i <= sam.top; i++) {
  62.         if (right_siz[i] >= k)
  63.             ans = max(ans, sam.maxl[i]);
  64.     }
  65.     return ans;
  66. }
  68. int main()
  69. {
  70.     printf("%d", solve());
  71.     return 0;
  72. }
  74. // 最终的树是信息合并过的树，因此维护right必须在加入节点时就+1

BZOJ3238: [Ahoi2013]差异

http://www.lydsy.com/JudgeOnline/upload/201306/1(4).jpg

SAM解法：前面两项只和长度有关很容易O(n)或O(1)做，那后面那个呢？展开看，就是求任意两个不相同后缀的最长公共前缀的和。这里需要一个重要的性质：将原串逆序插入后缀自动机得到一颗后缀树。而后缀树上两个元素的后缀是他们的LCA。显然我们树形dp设当前节点为LCA分别计算即可。元素两两相乘计算量很大怎么办啊？？用一下乘法分配率不就好了吗。

对于节点x，flag表示当前节点有没有后缀。我们要计算：

这也就是

  1. /**************************************************************
  2.     Problem: 3238
  3.     User: ljt12138
  4.     Language: C++
  5.     Result: Accepted
  6.     Time:3580 ms
  7.     Memory:131176 kb
  8. ****************************************************************/
  10. #include <bits/stdc++.h>
  11. using namespace std;
  13. const int MAXN = 500005*2, S = 26;
  15. long long right_siz[MAXN];
  17. struct SAM {
  18.     int chl[MAXN][S], fa[MAXN], maxl[MAXN];
  19.     int root, top, last;
  20.     void init()
  21.     {
  22.         memset(chl, 0, sizeof chl);
  23.         memset(fa, 0, sizeof fa);
  24.         memset(maxl, 0, sizeof maxl);
  25.         root = top = last = 1;
  26.     }
  27.     void push(int x)
  28.     {
  29.         int p = last, np = ++top; maxl[np] = maxl[p] + 1, right_siz[np]++;
  30.         while (p && !chl[p][x]) chl[p][x] = np, p = fa[p];
  31.         if (!p) fa[np] = root;
  32.         else {
  33.             int q = chl[p][x];
  34.             if (maxl[q] == maxl[p] + 1) fa[np] = q;
  35.             else {
  36.                 int nq = ++top; memcpy(chl[nq], chl[q], sizeof chl[q]);
  37.                 maxl[nq] = maxl[p] + 1, fa[nq] = fa[q], fa[q] = fa[np] = nq;
  38.                 while (p && chl[p][x] == q) chl[p][x] = nq, p = fa[p];
  39.             }
  40.         }
  41.         last = np;
  42.     }
  43. } sam;
  45. char str[MAXN];
  46. struct node {
  47.     int to, next;
  48. } edge[MAXN];
  49. int head[MAXN], top = 0;
  50. void push(int i, int j)
  51. { ++top, edge[top] = (node) {j, head[i]}, head[i] = top; }
  53. long long ans = 0;
  55. void dfs(int nd)
  56. {   
  57.     long long sum = right_siz[nd];
  58.     for (int i = head[nd]; i; i = edge[i].next) 
  59.         dfs(edge[i].to), right_siz[nd] += right_siz[edge[i].to], sum += right_siz[edge[i].to]*right_siz[edge[i].to];
  60.     ans += (right_siz[nd]*right_siz[nd]-sum)*sam.maxl[nd];
  61. }
  63. void work()
  64. {
  65.     memset(head, 0, sizeof head);
  66.     sam.init();
  67.     scanf("%s", str);
  68.     for (int i = strlen(str)-1; i >= 0; i--)
  69.         sam.push(str[i]-'a');
  70.     for (int i = 1; i <= sam.top; i++)
  71.         if (sam.fa[i]) push(sam.fa[i], i);
  72.     int n = strlen(str);
  73.     dfs(sam.root);
  74.     long long ret = 0;
  75.     for (long long i = n-1; i >= 1; i--) ret += i*(i+1)+(1+i)*i/2;
  76.     printf("%lld\n", ret-ans);
  77. }
  79. int main()
  80. {
  81.     work();
  82.     return 0;
  83. }
  84. 

ZJOI2015 诸神眷顾的幻想乡

给定一个叶节点不超过20的无根树，每个节点有一个字母。问树上路径形成的本质不同的字符串的个数。

广义后缀自动机裸题。从每个叶节点做bfs，记录父亲的状态从而插入建立后缀自动机。我们知道一个后缀自动机本质不同的子串个数为 ，或者DAG上dp即可。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 100001*20, S = 10;
  5. struct SAM {
  6.     int chl[MAXN][S], fa[MAXN], maxl[MAXN];
  7.     int top, root, last;
  8.     void init()
  9.     {
  10.         top = root = last = 1;
  11.         memset(chl, 0, sizeof chl);
  12.         memset(fa, 0, sizeof fa);
  13.         memset(maxl, 0, sizeof maxl);
  14.     }
  15.     void push(int stat, int x)
  16.     {
  17.         int p = stat, np = ++top; maxl[np] = maxl[p] + 1;
  18.         while (p && !chl[p][x]) chl[p][x] = np, p = fa[p];
  19.         if (!p) fa[np] = root;
  20.         else {
  21.             int q = chl[p][x];
  22.             if (maxl[q] == maxl[p] + 1) fa[np] = q;
  23.             else {
  24.                 int nq = ++top; maxl[nq] = maxl[p] + 1;
  25.                 memcpy(chl[nq], chl[q], sizeof chl[q]);
  26.                 fa[nq] = fa[q], fa[q] = fa[np] = nq;
  27.                 while (p && chl[p][x] == q) chl[p][x] = nq, p = fa[p];
  28.             }
  29.         }
  30.         last = np;
  31.     }
  32. }sam;
  34. queue<int> que;
  35. int stat[102400], rd[102400], col[102400];
  37. struct node {
  38.     int to, next;
  39. } edge[202400];
  40. int head[102400], top = 0;
  41. void push(int i, int j)
  42. { rd[i]++, ++top, edge[top] = (node) {j, head[i]}, head[i] = top; } 
  44. void bfs(int nd)
  45. {
  46.     //printf("BFS : %d\n", nd);
  47.     memset(stat, 0, sizeof stat);
  48.     stat[nd] = 1;
  49.     que.push(nd);
  50.     while (!que.empty()) {
  51.         int tp = que.front(); que.pop();
  52.         sam.push(stat[tp], col[tp]);
  53.         //printf("%d -- %d--+%d-->%d\n", tp, stat[tp], col[tp], sam.last);
  54.         for (int i = head[tp]; i; i = edge[i].next)
  55.             if (!stat[edge[i].to])
  56.                 stat[edge[i].to] = sam.last, que.push(edge[i].to);
  57.     }
  58. }
  60. int n, c;
  62. void solve()
  63. {
  64.     sam.init();
  65.     scanf("%d%d", &n, &c);
  66.     for (int i = 1; i <= n; i++)
  67.         scanf("%d", &col[i]);
  68.     for (int i = 1; i < n; i++) {
  69.         int u, v; scanf("%d%d", &u, &v);
  70.         push(u, v); push(v, u);
  71.     }
  72.     for (int i = 1; i <= n; i++)
  73.         if (rd[i] == 1)
  74.             bfs(i); 
  75.     long long ans = 0;
  76.     for (int i = 2; i <= sam.top; i++)
  77.         ans += sam.maxl[i] - sam.maxl[sam.fa[i]];
  78.     printf("%lld", ans);
  79. }
  81. int main()
  82. {
  83.     solve();
  84.     return 0;
  85. }

POI2000 公共串

给你个长度不超过2000的字符串，求最长公共子串。

SAM解法：只要在匹配的时候记录每个节点对于第i个串匹配的最长距离，然后xjb取max和min就好了。

  2. #include <bits/stdc++.h>
  3. using namespace std;
  5. const int MAXN = 2005*2, S = 26;
  7. struct SAM {
  8.     int chl[MAXN][S], fa[MAXN], maxl[MAXN];
  9.     int top, root, last;
  10.     void clear()
  11.     { top = root = last = 1; }
  12.     SAM() 
  13.     { clear(); }
  14.     void push(int x)
  15.     {
  16.         int p = last, np = ++top; maxl[np] = maxl[p]+1;
  17.         while (p && !chl[p][x]) chl[p][x] = np, p = fa[p];
  18.         if (!p) fa[np] = root;
  19.         else {
  20.             int q = chl[p][x]; 
  21.             if (maxl[q] == maxl[p]+1) fa[np] = q;
  22.             else {
  23.                 int nq = ++top; maxl[nq] = maxl[p] + 1;
  24.                 memcpy(chl[nq], chl[q], sizeof chl[q]);
  25.                 fa[nq] = fa[q], fa[q] = fa[np] = nq;
  26.                 while (p && chl[p][x] == q) chl[p][x] = nq, p = fa[p];
  27.             }
  28.         }
  29.         last = np;
  30.     }
  31. } sam;
  33. int n;
  34. int match_max[MAXN*2][10]; // 第j个串匹配到自动机上i节点时最长长度 
  35. char str[MAXN][10];
  37. void work()
  38. {
  39.     scanf("%d", &n);
  40.     scanf("%s", str[1]+1);
  41.     for (char *p = str[1]+1; *p != '\0'; p++) sam.push(*p-'a');
  42.     for (int i = 2; i <= n; i++) {
  43.         scanf("%s", str[i]+1);
  44.         int nd = sam.root, len = strlen(str[i]+1), mcd = 0;
  45.         for (int j = 1; j <= len; j++) {
  46.             if (sam.chl[nd][str[i][j]-'a']) {
  47.                 nd = sam.chl[nd][str[i][j]-'a'], mcd++;
  48.             } else {
  49.                 while (nd && !sam.chl[nd][str[i][j]-'a']) nd = sam.fa[nd];
  50.                 if (nd) mcd = sam.maxl[nd] + 1, nd = sam.chl[nd][str[i][j]-'a'];
  51.                 else nd = sam.root, mcd = 0;
  52.             } 
  53.             for (int k = nd; k; k = sam.fa[k]) match_max[k][i] = max(match_max[k][i], min(sam.maxl[k],mcd));
  54.         }
  55.     }
  56.     int ans = 0;
  57.     for (int i = 2; i <= sam.top; i++) {
  58.         int cnt = INT_MAX;
  59.         for (int j = 2; j <= n; j++) cnt = min(cnt, match_max[i][j]);
  60.         ans = max(ans, cnt); 
  61.     }
  62.     cout << ans << endl;
  63. }
  65. int main()
  66. {
  67.     work();
  68.     return 0;
  69. }
  72. /*Description
  75.        给出几个由小写字母构成的单词，求它们最长的公共子串的长度。
  76. 任务：
  77. l        读入单词
  78. l        计算最长公共子串的长度
  79. l        输出结果
  81. Input
  84. 文件的第一行是整数 n，1<=n<=5，表示单词的数量。接下来n行每行一个单词，只由小写字母组成，单词的长度至少为1，最大为2000。
  86. Output
  88. 仅一行，一个整数，最长公共子串的长度。
  91. */

APIO2014 回文串

给定一个字符串，求一个回文子串，最大化 ， 为出现次数。

首先我们用manacher算法求出本质不同的回文串。由于manacher的复杂度为，回文串个数为。我们一个个询问其出现次数即可。现在问题转化为了对于一个子串，要在 的时间内求出其出现次数。

首先我们预处理出在后缀自动机中的位置，那么 就是parent树上最后一个maxl大于l-r+1的节点。用倍增处理即可。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 300005*2, S = 26;
  6. int pos[MAXN]; // S[1..r]对应状态
  7. int fa[MAXN][21];
  8. char str[MAXN];
  9. int right_siz[MAXN];
  10. int stk[MAXN], top = 0, rd[MAXN];
  12. struct SAM {
  13.     int chl[MAXN][S], fa[MAXN], maxl[MAXN];
  14.     int top, root, last;
  15.     void clear()
  16.     {
  17.         top = root = last = 1;
  18.         memset(chl, 0, sizeof chl), memset(fa, 0, sizeof fa), memset(maxl, 0, sizeof maxl);
  19.     }
  20.     SAM() { clear(); }
  21.     void push(int x)
  22.     {
  23.         int p = last, np = ++top; maxl[np] = maxl[p] + 1, right_siz[np]++;
  24.         while (p && !chl[p][x]) chl[p][x] = np, p = fa[p];
  25.         if (!p) fa[np] = root;
  26.         else {
  27.             int q = chl[p][x]; 
  28.             if (maxl[q] == maxl[p] + 1) fa[np] = q;
  29.             else {
  30.                 int nq = ++top; maxl[nq] = maxl[p]+1;
  31.                 memcpy(chl[nq], chl[q], sizeof chl[q]);
  32.                 fa[nq] = fa[q], fa[q] = fa[np] = nq;
  33.                 while (p && chl[p][x] == q) chl[p][x] = nq, p = fa[p];
  34.             }
  35.         }
  36.         last = np;
  37.     }
  38. } sam;
  40. void top_sort()
  41. {
  42.     for (int i = 1; i <= sam.top; i++) rd[sam.fa[i]]++;
  43.     for (int i = 1; i <= sam.top; i++) if (rd[i] == 0) stk[++top] = i;
  44.     while (top) {
  45.         int t = stk[top--];  rd[sam.fa[t]]--, right_siz[sam.fa[t]] += right_siz[t];
  46.         if (rd[sam.fa[t]] == 0) stk[++top] = sam.fa[t];
  47.     }
  48. }
  50. void init()
  51. {
  52.     scanf("%s", str+1);
  53.     for (char *p = str+1; *p != '\0'; ++p)
  54.         sam.push(*p-'a');
  55.     int len = strlen(str+1);
  56.     for (int i = 1, nd = sam.root; i <= len; i++) {
  57.         nd = sam.chl[nd][str[i]-'a'];
  58.         pos[i] = nd;
  59.     }
  60.     for (int i = 1; i <= sam.top; i++) fa[i][0] = sam.fa[i];
  61.     for (int j = 1; j <= 20; j++)
  62.         for (int i = 1; i <= sam.top; i++)
  63.             fa[i][j] = fa[fa[i][j-1]][j-1];
  64.     top_sort(); // Count right_siz
  65. } 
  67. long long ans = 0;
  68. void query(int i, int j)
  69. {
  70.     int nd = pos[j];
  71.     for (int k = 20; k >= 0; k--)
  72.         if (sam.maxl[fa[nd][k]] >= j-i+1)
  73.             nd = fa[nd][k];
  74.     ans = max(ans, (long long)(j-i+1)*right_siz[nd]);
  75. }
  77. int p[MAXN];
  79. void work()
  80. {
  81.     int len = strlen(str+1);
  82.     int id = 0, mx = 0; // manacher
  83.     str[0] = '$'; 
  84.     for (int i = 1; i <= len; i++) {
  85.         if (mx > i) p[i] = min(p[id-(i-id)], mx-i); else p[i] = 1, query(i, i);
  86.         while (str[i-p[i]] == str[i+p[i]]) query(i-p[i], i+p[i]), p[i]++;
  87.         if (i+p[i] > mx) id = i, mx = i+p[i]; 
  88.     }
  89.     id = mx = 0;
  90.     for (int i = 1; i <= len; i++) {
  91.         if (mx > i) p[i] = min(p[id-(i-id)], mx-i); else p[i] = 0;
  92.         while (str[i-p[i]] == str[i+p[i]+1]) query(i-p[i], i+p[i]+1), p[i]++;
  93.         if (i+p[i] > mx) id = i, mx = i+p[i];
  94.     }
  95.     cout << ans << endl;
  96. }
  98. int main()
  99. {
  100.     init();
  101.     work();
  102.     return 0;
  103. }

HAOI2016找相同字符

给定两个串S1，S2，统计他们的公共子串总数。两个子串不同，当且仅当长度不同或出现位置不同。

SA解法：将S1和S2用一个'#'隔开，求出height数组，由于公共子串是后缀的前缀，因此答案就是所有前一半的后缀和后一半的后缀的lcp的和。用单调栈扫两遍记录答案即可。最优复杂度。

SAM解法：这个做法比较鬼畜。先把第一个串建立后缀自动机，再把第二个串在上面跑。到达一个状态x时匹配长度为len对答案的贡献分为两部分：

  1. 当前位置的收获
  2. 由于匹配了当前位置，自然匹配了父亲节点，就有 为的祖先

第一部分为，第二部分可以拓扑排序后 预处理。总复杂度为。

SA(DA)+单调栈，配合一些常数优化的技巧：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int maxn = 400005;
  5. struct SA {
  6.     int A[maxn], sa[maxn], rank[maxn], C[maxn], height[maxn], n;
  7.     struct radix_ele {
  8.         int id;
  9.         int k[2];
  10.         radix_ele() {}
  11.         radix_ele(int a, int b, int c):id(a){ k[0] = b, k[1] = c; }
  12.     } RE[maxn], RT[maxn];
  13.     void radix_sort()
  14.     {
  15.         for (register int y = 1; y >= 0; y--) {
  16.             memset(C, 0, sizeof C);
  17.             for (register int i = 1; i <= n; i++) C[RE[i].k[y]]++;
  18.             for (register int i = 1; i < maxn; i++) C[i] += C[i-1];
  19.             for (register int i = n; i >= 1; i--) RT[C[RE[i].k[y]]--] = RE[i];
  20.             for (register int i = 1; i <= n; i++) RE[i] = RT[i];
  21.         }
  22.         for (register int i = 1; i <= n; i++) {
  23.             rank[RE[i].id] = rank[RE[i-1].id];
  24.             if (RE[i].k[0] != RE[i-1].k[0] || RE[i].k[1] != RE[i-1].k[1])
  25.                 rank[RE[i].id]++;
  26.         }
  27.     }
  28.     void calc_rank()
  29.     {
  30.         for (int i = 1; i <= n; i++) RE[i] = radix_ele(i, A[i], 0);
  31.         radix_sort();
  32.         for (register int k = 1; k < n; k <<= 1) {
  33.             for (register int i = 1; i <= n; i++) RE[i] = radix_ele(i, rank[i], i+k<=n?rank[i+k]:0);
  34.             radix_sort();
  35.         }
  36.         for (register int i = 1; i <= n; i++) sa[rank[i]] = i;
  37.     }
  38.     void calc_height()
  39.     {
  40.         int h = 0;
  41.         for (int i = 1; i <= n; i++) {
  42.             if (rank[i] == 1) h = 0;
  43.             else {
  44.                 int k = sa[rank[i]-1];
  45.                 if (--h < 0) h = 0;
  46.                 while (A[i+h] == A[k+h]) h++;
  47.             }
  48.             height[rank[i]] = h;
  49.         }
  50.     }
  51.     inline void init()
  52.     {
  53.         calc_rank();
  54.         calc_height();
  55.     }
  56. } SA;
  58. int n1, n2;
  59. char str1[200005], str2[200005];
  61. struct mono_stack {
  62.     struct ele {
  63.         int dat, cnt;
  64.         ele(){}
  65.         ele(int a, int b):dat(a), cnt(b){}
  66.     } stk[400005];
  67.     int top;
  68.     long long ans;
  69.     mono_stack():ans(0){ top = 0; }
  70.     void init()
  71.     {
  72.         ans = top = 0;
  73.     }
  74.     inline void push(int i, int put) // put 是否放入
  75.     {
  76.         int cnt = put;
  77.         for (; top && stk[top].dat >= i; top--) {
  78.             cnt += stk[top].cnt;
  79.             ans -= stk[top].cnt*(stk[top].dat - i);
  80.         }
  81.         ans += put*i;
  82.         if (cnt) stk[++top] = ele(i, cnt);
  83.     }
  84. }stk;
  86. int main()
  87. {
  88.     gets(str1);
  89.     gets(str2);
  90.     n1 = strlen(str1), n2 = strlen(str2);
  91.     SA.n = n1 + n2 + 1;
  92.     for (register int i = 1; i <= n1; i++) SA.A[i] = str1[i-1] - 'a' + 1; SA.A[n1+1] = 27;
  93.     for (register int i = 1; i <= n2; i++) SA.A[n1+1+i] = str2[i-1] - 'a' + 1;
  94.     SA.init();
  95.     long long ans = 0;
  96.     stk.init();
  97.     for (register int i = 1; i < SA.n; i++) {
  98.         if (SA.sa[i] <= n1) ans += stk.ans, stk.push(SA.height[i+1], 0);
  99.         else stk.push(SA.height[i+1], 1);
  100.     }
  101.     stk.init();
  102.     for (register int i = 1; i < SA.n; i++) {
  103.         if (SA.sa[i] > n1+1) ans += stk.ans, stk.push(SA.height[i+1], 0);
  104.         else stk.push(SA.height[i+1], 1);
  105.     }
  106.     cout << ans << endl;
  107.     return 0;
  108. }

SAM:

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 200005*2, S = 26;
  5. int right_siz[MAXN];
  7. struct SAM {
  8.     int chl[MAXN][S], fa[MAXN], maxl[MAXN];
  9.     int top, root, last;
  10.     void clear() 
  11.     { top = root = last = 1; }
  12.     SAM()
  13.     { clear(); }
  14.     void push(int x)
  15.     {
  16.         int p = last, np = ++top; maxl[np] = maxl[p] + 1; right_siz[np]++;
  17.         while (p && !chl[p][x]) chl[p][x] = np, p = fa[p];
  18.         if (!p) fa[np] = root;
  19.         else {
  20.             int q = chl[p][x];
  21.             if (maxl[q] == maxl[p] + 1) fa[np] = q;
  22.             else {
  23.                 int nq = ++top; maxl[nq] = maxl[p] + 1;
  24.                 memcpy(chl[nq], chl[q], sizeof chl[q]);
  25.                 fa[nq] = fa[q], fa[q] = fa[np] = nq;
  26.                 while (p && chl[p][x] == q) chl[p][x] = nq, p = fa[p];
  27.             }
  28.         }
  29.         last = np;
  30.     }
  31. } sam;
  33. char s1[MAXN], s2[MAXN];
  35. int stk[MAXN], top = 0;
  36. int rd[MAXN];
  37. int topo[MAXN], tp_top = 0;
  38. int canc[MAXN];
  39. int vis[MAXN];
  41. void dfs(int nd, string str) 
  42. {
  43.     printf("Id = %d, pre = %d, dis = %d, right = %d, cacc = %d\n", nd, sam.fa[nd], sam.maxl[nd], right_siz[nd], canc[nd]);
  44.     vis[nd] = 1;
  45.     for (int i = 0; i < S; i++)
  46.         if (sam.chl[nd][i])
  47.             printf("-+%c-> %d\n", i+'a', sam.chl[nd][i]);
  48.     for (int i = 0; i < S; i++)
  49.         if (sam.chl[nd][i] && !vis[sam.chl[nd][i]])
  50.             dfs(sam.chl[nd][i], str+char(i+'a'));
  51. }
  53. void top_sort()
  54. {
  55.     for (int i = 1; i <= sam.top; i++) rd[sam.fa[i]]++;
  56.     for (int i = 1; i <= sam.top; i++) if (rd[i] == 0) stk[++top] = i;
  57.     while (top) {
  58.         int t = stk[top--]; topo[++tp_top] = t, rd[sam.fa[t]]--;
  59.         if (rd[sam.fa[t]] == 0) stk[++top] = sam.fa[t];
  60.     }
  61.     for (int i = 1; i <= tp_top; i++) right_siz[sam.fa[topo[i]]] += right_siz[topo[i]];
  62.     for (int i = tp_top; i >= 1; i--) 
  63.         if (topo[i] != sam.root && sam.fa[topo[i]] != sam.root) 
  64.             canc[topo[i]] = canc[sam.fa[topo[i]]] + (sam.maxl[sam.fa[topo[i]]]-sam.maxl[sam.fa[sam.fa[topo[i]]]])*right_siz[sam.fa[topo[i]]];
  65. }
  67. void work()
  68. {
  69.     scanf("%s%s", s1, s2);
  70.     for (char *p = s1; *p != '\0'; p++) sam.push(*p-'a');
  71.     top_sort();
  72.     int nd = sam.root, len = 0;
  73.     long long ans = 0;
  74.     for (char *p = s2; *p != '\0'; p++) {
  75.         if (sam.chl[nd][*p-'a']) nd = sam.chl[nd][*p-'a'], len++;
  76.         else {
  77.             while (nd && !sam.chl[nd][*p-'a']) nd = sam.fa[nd];
  78.             if (!nd) nd = sam.root, len = 0;
  79.             else len = sam.maxl[nd]+1, nd = sam.chl[nd][*p-'a'];
  80.         }
  81.         ans += canc[nd] + (len-sam.maxl[sam.fa[nd]])*right_siz[nd];
  82.     }
  83.     cout << ans << endl;
  84. }
  86. int main()
  87. {
  88.     work();
  89.     return 0;
  90. }

BZOJ 2555: SubString

给你一个字符串init，要求你支持两个操作
(1):在当前字符串的后面插入一个字符串
(2):询问字符串s在当前字符串中出现了几次？(作为连续子串)
你必须在线支持这些操作。

SAM+LCT解法：由于SAM是一个在线结构，只要动态维护right集合大小，再暴力匹配后查询right集合大小即可。

用lct维护时的技巧：由于涉及有根树换根，自底向上传送比较困难，考虑自顶向下维护right。操作分别是：

: 先连接，access(y)，splay(y)，将y和y的左子树siz都加上siz[x]，可以用lazy_tag实现。

：先切割，access(y)，splay(y)，将y和y的左子树都减去siz[x]，仍然lazy_tag。

写的时候一定要小心再小心，不然一上午就荒废了。别问我是怎么知道的。

  1. /**************************************************************
  2.     Problem: 2555
  3.     User: ljt12138
  4.     Language: C++
  5.     Result: Accepted
  6.     Time:26356 ms
  7.     Memory:404428 kb
  8. ****************************************************************/
  10. #include <bits/stdc++.h>
  11. using namespace std;
  13. const int MAXN = 1600002, S = 26;
  15. struct LCT {
  16.     int chl[MAXN][2], fa[MAXN], siz[MAXN], flag[MAXN], rev[MAXN], add[MAXN];
  17.     int stk[MAXN];
  18.     int root, top;
  19.     void clear()
  20.     { root = top = 0; }
  21.     LCT()
  22.     { clear(); }
  23.     bool isrt(int nd)
  24.     { return chl[fa[nd]][0] != nd && chl[fa[nd]][1] != nd; }
  25.     void pdw(int nd)
  26.     {
  27.         int &lc = chl[nd][0], &rc = chl[nd][1];
  28.         if (lc) rev[lc] ^= rev[nd], add[lc] += add[nd];
  29.         if (rc) rev[rc] ^= rev[nd], add[rc] += add[nd];
  30.         if (rev[nd]) rev[nd] = 0, swap(lc, rc);
  31.         if (add[nd]) siz[nd] += add[nd], add[nd] = 0;
  32.     }
  33.     void zig(int nd)
  34.     {
  35.         int p = fa[nd], g = fa[p];
  36.         int tp = chl[p][0] != nd, tg = chl[g][0] != p, son = chl[nd][tp^1];
  37.         if (!isrt(p)) chl[g][tg] = nd;
  38.         chl[nd][tp^1] = p, chl[p][tp] = son;
  39.         fa[nd] = g, fa[p] = nd, fa[son] = p;
  40.     }
  41.     void splay(int nd)
  42.     {
  43.         int top = 0; stk[++top] = nd;
  44.         for (int x = nd; !isrt(x); x = fa[x])
  45.             stk[++top] = fa[x];
  46.         while (top) pdw(stk[top--]);
  47.         while (!isrt(nd)) {
  48.             int p = fa[nd], g = fa[p];
  49.             int tp = chl[p][0] != nd, tg = chl[g][0] != p;
  50.             if (isrt(p)) { zig(nd); break; }
  51.             else if (tp == tg) zig(p), zig(nd);
  52.             else zig(nd), zig(nd);
  53.         }
  54.     }
  55.     void dfs(int nd, int tab)
  56.     {
  57.         if (!nd) return;
  58.         for (int i = 1; i <= tab; i++) putchar(' ');
  59.         printf("nd = %d, flag = %d, siz = %d, lc = %d, rc = %d, fa = %d, rev = %d\n", nd, flag[nd], siz[nd], chl[nd][0], chl[nd][1], fa[nd], rev[nd]);
  60.         dfs(chl[nd][0], tab+2);
  61.         dfs(chl[nd][1], tab+2);
  62.     }
  63.     void access(int x)
  64.     {
  65.         for (int y = 0; x; x = fa[y = x])
  66.             splay(x), chl[x][1] = y;
  67.     }
  68.     void mkt(int x)
  69.     { access(x), splay(x), rev[x] ^= 1; }
  70.     void link(int x, int y)
  71.     { mkt(x); splay(x); fa[x] = y; }
  72.     void cut(int x, int y)
  73.     { mkt(x), access(y), splay(y), fa[x] = chl[y][0] = 0;}
  74.     void lct_link(int x, int y) // x->y
  75.     {
  76.         link(x, y), mkt(1);
  77.         access(y), splay(y), siz[y] += siz[x];
  78.         if (chl[y][0]) add[chl[y][0]] += siz[x];
  79.     }
  80.     void lct_cut(int x, int y) // cut x->y
  81.     {
  82.         cut(x, y), mkt(1);
  83.         access(y), splay(y), siz[y] -= siz[x];
  84.         if (chl[y][0]) add[chl[y][0]] -= siz[x];
  85.     }
  86.     void set_flag(int x)
  87.     { mkt(x), splay(x), siz[x] = 1; }
  88.     int find_fa(int x)
  89.     {
  90.         access(x);
  91.         while (!isrt(x)) x = fa[x];
  92.         return x;
  93.     }
  94.     int query(int nd)
  95.     {
  96.         mkt(nd), splay(nd);
  97.         return siz[nd];
  98.     }
  99. } lct;
  101. struct SAM {
  102.     int chl[MAXN*2][S], fa[MAXN*2], maxl[MAXN*2];
  103.     int top, last, root;
  104.     void clear()
  105.     { top = last = root = 1; }
  106.     SAM()
  107.     { clear(); }
  108.     void push(int x)
  109.     {
  110.         int p = last, np = ++top; maxl[np] = maxl[p] + 1; lct.set_flag(np);
  111.         while (p && !chl[p][x]) chl[p][x] = np, p = fa[p];
  112.         if (!p) fa[np] = root, lct.lct_link(np, root);
  113.         else {
  114.             int q = chl[p][x];
  115.             if (maxl[q] == maxl[p] + 1) fa[np] = q, lct.lct_link(np, q);
  116.             else {
  117.                 int nq = ++top; maxl[nq] = maxl[p] + 1;
  118.                 memcpy(chl[nq], chl[q], sizeof chl[q]);
  119.                 lct.lct_link(nq, fa[q]), fa[nq] = fa[q];
  120.                 lct.lct_cut(q, fa[q]), lct.lct_link(q, nq), fa[q] = nq;
  121.                 lct.lct_link(np, nq), fa[np] = nq;
  122.                 while (p && chl[p][x] == q) chl[p][x] = nq, p = fa[p];
  123.             }
  124.         }
  125.         last = np;
  126.     }
  127. } sam;
  129. char str[MAXN*2];
  130. int q, mask = 0;
  132. void decode(int mask)
  133. {
  134.     int len = strlen(str);
  135.     for (int j = 0; j < len; j++) {
  136.         mask = (mask*131+j)%len;
  137.         swap(str[j], str[mask]);
  138.     }
  139. }
  141. void get_str(char str[])
  142. {
  143.     scanf("%s", str);
  144.     decode(mask);
  145. }
  147. char opt[10];
  148. int main()
  149. {
  150.     scanf("%d", &q);
  151.     scanf("%s", str);
  152.     for (char *p = str; *p != '\0'; p++)
  153.         sam.push(*p-'A');
  154.     for (int i = 1; i <= q; i++) {
  155.         scanf("%s", opt);
  156.         if (opt[0] == 'A') {
  157.             get_str(str);
  158.             for (char *p = str; *p != '\0'; p++)
  159.                 sam.push(*p-'A');
  160.         } else {
  161.             get_str(str);
  162.             int nd = sam.root, flag = 0;
  163.             for (char *p = str; *p != '\0'; p++) {
  164.                 if (!sam.chl[nd][*p-'A']) {flag = 1; break; }
  165.                 else nd = sam.chl[nd][*p-'A'];
  166.             }
  167.             if (flag) puts("0");
  168.             else {
  169.                 int ans = lct.query(nd);
  170.                 printf("%d\n", ans);
  171.                 mask ^= ans;
  172.             }
  173.         }
  174.     }
  175.     return 0;
  176. }

NOI2015 品酒大会

给你一个长度为的字符串，每个后缀有一个权值。，回答：

  1. 满足的后缀个数
  2. 满足的后缀权值之积的最大值

SA解法：SA配合并查集。
SAM解法：将串逆序插入SAM得到后缀树，然后后缀树上dp即可。
我们知道一个串逆序插入后缀树如同aabb插入为bbaa，每一个前缀都是原串的后缀，因此加入时打过flag的节点都是后缀标记的位置。节点x对应的是原串的字符串末尾长度构成的后缀。

嘴巴AC倒是挺容易，然后一下午就没了

几个细节：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 600005, S = 26;
  5. struct SAM {
  6.     int chl[MAXN][S], fa[MAXN], maxl[MAXN], flag[MAXN],vis[MAXN];
  7.     int top, last, root;
  8.     void clear()
  9.     { top = last = root = 1; }
  10.     SAM()
  11.     { clear(); }
  12.     void dfs(int nd)
  13.     {
  14.         if (!nd || vis[nd]) return;
  15.         vis[nd] = 1;
  16.         printf("nd = %d, fa = %d, maxl = %d, flag = %d\n", nd, fa[nd], maxl[nd], flag[nd]);
  17.         for (int i = 0; i < S; i++)
  18.             dfs(chl[nd][i]);
  19.     }
  20.     void push(int x)
  21.     {
  22.         int p = last, np = ++top; maxl[np] = maxl[p] + 1, flag[np] = 1;
  23.         while (p && !chl[p][x]) chl[p][x] = np, p = fa[p];
  24.         if (!p) fa[np] = root;
  25.         else {
  26.             int q = chl[p][x];
  27.             if (maxl[q] == maxl[p] + 1) fa[np] = q;
  28.             else {
  29.                 int nq = ++top; maxl[nq] = maxl[p] + 1;
  30.                 memcpy(chl[nq], chl[q], sizeof chl[q]);
  31.                 fa[nq] = fa[q], fa[q] = fa[np] = nq;
  32.                 while (p && chl[p][x] == q) chl[p][x] = nq, p = fa[p];
  33.             }
  34.          }
  35.          last = np;
  36.     }
  37. } sam;
  39. char str[MAXN];
  40. long long a[MAXN];
  41. int n;
  43. struct node {
  44.     int to, next;
  45. } edge[MAXN];
  46. int head[MAXN], top = 0;
  47. void push(int i, int j)
  48. { ++top, edge[top] = (node) {j, head[i]}, head[i] = top; }
  49. long long siz[MAXN];
  50. long long mx[MAXN], mn[MAXN];
  51. long long rk[MAXN];
  53. void init()
  54. {
  55.     scanf("%d%s", &n, str+1);
  56.     for (int i = n; i >= 1; i--) scanf("%lld", &a[i]);
  57.     for (int i = n; i >= 1; i--) sam.push(str[i]-'a');
  58.     for (int i = 1; i <= sam.top; i++) if (sam.fa[i]) push(sam.fa[i], i);
  59.     for (int i = 0; i <= sam.top; i++) mx[i] = LONG_LONG_MIN, mn[i] = LONG_LONG_MAX;
  60. }
  62. long long rcnt[MAXN];
  63. long long maxcnt[MAXN];
  65. void dfs(int nd)
  66. {
  67.     siz[nd] = sam.flag[nd], rk[nd] = a[sam.maxl[nd]]*sam.flag[nd];
  68.     if (sam.flag[nd]) mx[nd] = mn[nd] = rk[nd];
  69.     for (int i = head[nd]; i; i = edge[i].next) {
  70.         int to = edge[i].to; dfs(to); siz[nd] += siz[to];
  71.         if (mx[nd] != LONG_LONG_MIN && mn[nd] != LONG_LONG_MAX && mx[to] != LONG_LONG_MIN && mn[to] != LONG_LONG_MAX)
  72.             maxcnt[sam.maxl[nd]] = max(maxcnt[sam.maxl[nd]], max(mx[to]*mx[nd], mn[to]*mn[nd]));
  73.         mx[nd] = max(mx[nd], mx[to]);
  74.         mn[nd] = min(mn[nd], mn[to]);
  75.     }
  76. }
  78. void work()
  79. {
  80.     for (int i = 0; i <= MAXN; i++) maxcnt[i] = LONG_LONG_MIN;
  81.     memset(rcnt, 0, sizeof rcnt);
  82.     init();
  83.     dfs(1);
  84.     for (int i = 2; i <= sam.top; i++) {
  85.         long long cnt = siz[i]*siz[i]-sam.flag[i];long long maxx = rk[i], maxs = LONG_LONG_MAX, minn = LONG_LONG_MIN, mins = LONG_LONG_MIN;
  86.         for (int k = head[i]; k; k = edge[k].next)
  87.             cnt -= siz[edge[k].to]*siz[edge[k].to];
  88.         rcnt[sam.maxl[i]] += cnt/2;
  89.     }
  90.     for (int i = n-2; i >= 0; i--) rcnt[i] += rcnt[i+1], maxcnt[i] = max(maxcnt[i], maxcnt[i+1]);
  91.     rcnt[0] = (long long)n*(n-1)/2;
  92.     for (int i = 0; i < n; i++) printf("%lld %lld\n", rcnt[i], maxcnt[i]!=LONG_LONG_MIN?maxcnt[i]:0);
  93. }
  95. int main()
  96. {
  97.     work();
  98.     return 0;
  99. }

bzoj3998 TJOI2015 弦论

Description

对于一个给定长度为N的字符串，求它的第K小子串是什么。
Input

好不容易理解了子串计数...总是混。

后缀自动机上路径与子串一一对应，一个位置对应的同一本质相同的子串出现次数为。因此需要预处理出这一节点之后走出的路径个数，然后贪心的找即可。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 1000005, S = 26;
  5. int t, k;
  7. struct SAM {
  8.     int chl[MAXN][S], fa[MAXN], maxl[MAXN], val[MAXN];
  9.     int top, root, last;
  10.     SAM() { top = root = last = 1; }
  11.     void push(int x)
  12.     {
  13.         int p = last, np = ++top; val[np]++;
  14.         while (p && !chl[p][x]) chl[p][x] = np, p = fa[p];
  15.         if (!p) fa[np] = root;
  16.         else {
  17.             int q = chl[p][x];
  18.             if (maxl[q] == maxl[p] + 1) fa[np] = q;
  19.             else {
  20.                 int nq = ++top; maxl[nq] = maxl[p] + 1;
  21.                 memcpy(chl[nq], chl[q], sizeof chl[q]);
  22.                 fa[nq] = fa[q], fa[q] = fa[np] = nq;
  23.                 while (p && chl[p][x] == q) chl[p][x] = nq, p = fa[p];
  24.             }
  25.         }
  26.         last = np;
  27.     }
  28.     int stk[MAXN], top_tp, rd[MAXN], topo[MAXN];
  29.     void top_sort()
  30.     {
  31.         for (int i = 1; i <= top; i++) rd[fa[i]]++;
  32.         for (int i = 1; i <= top; i++) if (rd[i] == 0) stk[++top_tp] = i;
  33.         int topo_ord = 0;
  34.         while (top_tp) {
  35.             int nd = stk[top_tp--]; rd[fa[nd]]--, val[fa[nd]] += val[nd], topo[++topo_ord] = nd;
  36.             if (rd[fa[nd]] == 0) stk[++top_tp] = fa[nd];
  37.         }
  38.         if (t == 0)
  39.             for (int i = 1; i <= top; i++) val[i] = 1;
  40.     }
  41. }sam;
  43. char str[MAXN];
  44. int siz[MAXN];
  46. void find(int nd, int k)
  47. {
  48.     if (k <= sam.val[nd]) return;
  49.     k -= sam.val[nd];
  50.     for (int i = 0; i < S; i++) if (sam.chl[nd][i]){
  51.         if (k <= siz[sam.chl[nd][i]]) {
  52.             putchar('a'+i);
  53.             find(sam.chl[nd][i], k);
  54.             return;
  55.         } else k -= siz[sam.chl[nd][i]];
  56.     }
  57. }
  59. void work()
  60. {
  61.     scanf("%s", str);
  62.     for (char *p = str; *p != '\0'; p++) sam.push(*p-'a');
  63.     scanf("%d%d", &t, &k);
  64.     sam.top_sort();
  65.     for (int i = 1; i <= sam.top; i++) {
  66.         int nd = sam.topo[i];
  67.         siz[nd] = sam.val[nd];
  68.         for (int j = 0; j < S; j++)
  69.             siz[nd] += siz[sam.chl[nd][j]];
  70.     }
  71.     sam.val[1] = 0;
  72.     if (siz[1] < k) puts("-1");
  73.     else find(1, k);
  74. }
  76. int main()
  77. {
  78.     work();
  79.     return 0;
  80. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注