[关闭]
@ljt12138 2017-04-16T15:59:57.000000Z 字数 13622 阅读 991

诸神眷顾的幻想乡

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

广义后缀自动机裸题。从每个叶节点做bfs，记录父亲的状态从而插入建立后缀自动机。我们知道一个后缀自动机本质不同的子串个数为 ∑imax[i]−min[i]+1=max[i]−max[fa[i]]，或者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.     //freopen("zjoi15_substring.in", "r", stdin);
  84.     //freopen("zjoi15_substring.out", "w", stdout);
  85.     solve();
  86.     return 0;
  87. }

POI2000 公共串

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

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

APIO2014 回文串

给定一个字符串S，求一个回文子串T，最大化 |T|∗times(T)，times(T) 为出现次数。

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

首先我们预处理出pos[r]:=S[1..r]在后缀自动机中的位置，那么 S[l,r] 就是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的和。用单调栈扫两遍记录答案即可。最优复杂度O(n)。

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

  1. 当前位置的收获 (len−min(x)+1)×|Right(x)|
  2. 由于匹配了当前位置，自然匹配了父亲节点，就有 ∑i为x的祖先(max(i)−min(i)+1)×|Right(i)|

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

  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.     //int l = strlen(s2); s2[l] = '$', s2[l+1] = '\0';
  75.     for (char *p = s2; *p != '\0'; p++) {
  76.         if (sam.chl[nd][*p-'a']) nd = sam.chl[nd][*p-'a'], len++;
  77.         else {
  78.             while (nd && !sam.chl[nd][*p-'a']) nd = sam.fa[nd];
  79.             if (!nd) nd = sam.root, len = 0;
  80.             else len = sam.maxl[nd]+1, nd = sam.chl[nd][*p-'a'];
  81.         }
  82.         ans += canc[nd] + (len-sam.maxl[sam.fa[nd]])*right_siz[nd];
  83.         //cout << ans << endl;
  84.     }
  85.     cout << ans << endl;
  86. }
  88. int main()
  89. {
  90.     work();
  91.     return 0;
  92. }

2555: SubString

LCT维护Right数组大小...

神题。

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

poj2774: Long Long Message

裸题，SAM直接碾。

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. using namespace std;
  6. const int MAXN = 200005;
  7. int chl[MAXN][26], fa[MAXN], maxl[MAXN];
  8. int top = 1, root = 1, last = 1;
  9. void push(int x)
  10. {
  11.     int p = last, np = ++top; maxl[np] = maxl[p]+1;
  12.     while (p && !chl[p][x]) chl[p][x] = np, p = fa[p];
  13.     if (!p) fa[np] = root;
  14.     else {
  15.         int q = chl[p][x];
  16.         if (maxl[q] == maxl[p]+1) fa[np] = q;
  17.         else {
  18.             int nq = ++top; maxl[nq] = maxl[p]+1;
  19.             memcpy(chl[nq], chl[q], sizeof chl[q]);
  20.             fa[nq] = fa[q], fa[q] = fa[np] = nq;
  21.             while (p && chl[p][x] == q) chl[p][x] = nq, p = fa[p];
  22.         }
  23.     }
  24.     last = np;
  25. }
  27. char str[MAXN];
  28. int main()
  29. {
  30.     scanf("%s", str);
  31.     for (char *p = str; *p != '\0'; ++p)
  32.         push(*p-'a');
  33.     scanf("%s", str);
  34.     int nd = root, len = 0, ans = 0;
  35.     for (char *p = str; *p != '\0'; ++p) {
  36.         int x = *p-'a';
  37.         if (chl[nd][x]) nd = chl[nd][x], len++;
  38.         else {
  39.             while (nd && !chl[nd][x]) nd = fa[nd];
  40.             if (!nd) nd = root, len = 0;
  41.             else len = maxl[nd]+1, nd = chl[nd][x];
  42.         }
  43.         ans = max(ans, len);
  44.     }
  45.     cout << ans << endl;
  46.     return 0;
  47. }

[SPOJ705]不同的子串

模板复习计划，裸题。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 50005*2;
  5. struct SAM {
  6.     int chl[MAXN][26], fa[MAXN], maxl[MAXN];
  7.     int top, root, last;
  8.     void clear()
  9.     { top = root = last = 1, memset(chl, 0, sizeof chl),
  10.     memset(fa, 0, sizeof fa), memset(maxl, 0, sizeof maxl); }
  11.     SAM() { clear(); }
  12.     void push(int stat, int x)
  13.     {
  14.         int p = last, np = ++top; maxl[np] = maxl[p]+1;
  15.         while (p && !chl[p][x]) chl[p][x] = np, p = fa[p];
  16.         if (!p) fa[np] = root;
  17.         else {
  18.             int q = chl[p][x];
  19.             if (maxl[q] == maxl[p]+1) fa[np] = q;
  20.             else {
  21.                 int nq = ++top; maxl[nq] = maxl[p]+1;
  22.                 memcpy(chl[nq], chl[q], sizeof chl[q]);
  23.                 fa[nq] = fa[q], fa[q] = nq, fa[np] = nq;
  24.                 while (p && chl[p][x] == q) chl[p][x] = nq, p = fa[p];
  25.             }
  26.         }
  27.         last = np;
  28.     }
  29. } sam;
  31. char str[MAXN];
  33. int main()
  34. {
  35.     freopen("subst1.in", "r", stdin);
  36.     freopen("subst1.out", "w", stdout);
  37.     scanf("%s", str+1);
  38.     for (char *p = str+1; *p != '\0'; ++p)
  39.         sam.push(sam.last, *p-'A');
  40.     long long ans = 0;
  41.     for (int i = 1; i <= sam.top; i++)
  42.         ans += sam.maxl[i]-sam.maxl[sam.fa[i]];
  43.     cout << ans << endl;
  44.     return 0;
  45. }

bzoj2806: [Ctsc2012]Cheat

比较神的题...
后缀自动机上dp，由于dp决策有区间性质，可以用线段树或者单调队列维护。线段树版本(O(nlg2n))会TLE，明天写单调队列的。

线段树(TLE):

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 1100001*2;
  5. int tree[MAXN][2], fin[MAXN], col[MAXN], trie_root = 0, trie_top = 0;
  6. void push_str(int &nd, const char *str)
  7. {
  8.     if (!nd) nd = ++trie_top;
  9.     if (*str == '\0') fin[nd] = 1;
  10.     else push_str(tree[nd][*str-'0'], str+1), col[tree[nd][*str-'0']] = *str-'0';
  11. }
  13. int chl[MAXN][2], fa[MAXN], maxl[MAXN], root = 1, top = 1;
  14. void push(int p, int x, int &last)
  15. {
  16.     int 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.             chl[nq][0] = chl[q][0], chl[nq][1] = chl[q][1];
  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. }
  32. queue<int> que;
  33. int stat[MAXN];
  35. void build_tree()
  36. {
  37.     que.push(trie_root), stat[trie_root] = 1;
  38.     while (!que.empty()) {
  39.         int tp = que.front(); que.pop();
  40.         int last;
  41.         push(stat[tp], col[tp], last);
  42.         for (int i = 0; i <= 1; i++)
  43.             if (tree[tp][i])
  44.                 stat[tree[tp][i]] = last, que.push(tree[tp][i]);
  45.     }
  46. }
  48. bool match(char str[], int l, int r)
  49. {
  50.     if (l <= 0 || l > r) return 0;
  51.     int nd = root, ans = 0, len = 0;
  52.     for (int i = l; i <= r; i++) {
  53.         int x = str[i]-'0';
  54.         if (chl[nd][x]) nd = chl[nd][x], len++;
  55.         else {
  56.             while (nd && !chl[nd][x]) nd = fa[nd];
  57.             if (!nd) nd = root, len = 0;
  58.             else len = maxl[nd]+1, nd = chl[nd][x];
  59.         }
  60.         ans = max(ans, len);
  61.     } 
  62.     return ans == r-l+1;
  63. }
  65. char str[MAXN];
  66. int dp[MAXN], max_back[MAXN];
  67. int n, m;
  69. int zkw[(1<<21)+1], N = 1<<20;
  70. void modify(int nd, int val)
  71. {
  72.     nd += N-1;
  73.     zkw[nd] = val;
  74.     for (int i = nd>>1; i; i >>= 1)
  75.         zkw[i] = max(zkw[i*2], zkw[i*2+1]);
  76. }
  77. int ask_max(int l, int r)
  78. {
  79.     if (l > r) return 0;
  80.     int ans = -233333333;
  81.     for (l += N-1, r += N-1; l < r; l>>=1, r>>=1) {
  82.         if (l&1) ans = max(ans, zkw[l++]);
  83.         if (!(r&1)) ans = max(ans, zkw[r--]);
  84.     }
  85.     if (l == r) ans = max(ans, zkw[l]);
  86.     return ans;
  87. }
  89. bool do_dp(int L)
  90. {
  91.     int l = strlen(str+1);
  92.     memset(dp, 0, sizeof dp);
  93.     memset(zkw, -127/3, sizeof zkw);
  94.     int max_val = 0;
  95.     modify(0, 0);
  96.     for (int i = 1; i <= l; i++) {
  97.         dp[i] = max_val;
  98.         if (i-L >= 0 && max_back[i] <= i-L)
  99.             dp[i] = max(dp[i], i+ask_max(max_back[i], i-L));
  100.         max_val = max(max_val, dp[i]);
  101.         modify(i, dp[i]-i);
  102.     }
  103.     return dp[l]*10 >= l*9;
  104. }
  106. int main()
  107. {
  108.     scanf("%d%d", &n, &m);
  109.     for (int i = 1; i <= m; i++) {
  110.         scanf("%s", str);
  111.         push_str(trie_root, str);
  112.     }
  113.     build_tree();
  114.     for (int i = 1; i <= n; i++) {
  115.         scanf("%s", str+1);
  116.         memset(max_back, 0, sizeof max_back);
  117.         for (int i = 1, l = strlen(str+1); i <= l; i++) {
  118.             int lf = 1, rt = i, mid;
  119.             while (lf <= rt) {
  120.                 mid = (lf+rt)>>1;
  121.                 if (match(str, i-mid+1, i)) lf = mid+1;
  122.                 else rt = mid-1;
  123.             }
  124.             max_back[i] = i-(lf-1);
  125.         } 
  126.         int l = 1, r = strlen(str+1), mid;
  127.         while (l <= r) {
  128.             mid = (l+r)>>1;
  129.             if (do_dp(mid)) l = mid+1;
  130.             else r = mid-1;
  131.         }
  132.         printf("%d\n", l-1);
  133.     }
  134.     return 0;
  135. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注