[SPOJ]NSUBSTR
转载请注明出处：http://danihao123.is-programmer.com/
第一次做了一道有一定难度的SAM题……
考虑每个SAM上的结点x，他的子串表示范围一定是一个区间[Min(x),Max(x)]，然后他的Right(x)的大小就是该点所代表的每个子串的出现次数。
那么考虑怎么搞出这个|Right(x)|。我们把每个“实点”（就是在SAM每一次插入后成为last的结点）的点权钦定为1，其他搞成0。然后每个点的|Right(x)|就是x在Right树上的子树的点权和。
然后接下来看上去可以直接做……但是区间chkmax这种黑暗操作，是不是要涉及毒瘤数据结构？
答案是否定的。任何短的子串都是某一个长子串的子串，所以说我们只需要在Max(x)那个地方chkmax，然后搞个后缀最大值即可。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | #include <cstdio>#include <cstring>#include <cstdlib>#include <cctype>#include <algorithm>#include <utility>#include <queue>const int maxn = 250005;const int sigma_siz = 26;struct Node { int maxl, rs; Node *fa; Node *ch[sigma_siz];};Node pool[maxn << 1]; Node *tot = pool;Node *rt = tot, *last = tot;void extend(int c) { Node *np = ++ tot; np -> maxl = last -> maxl + 1; np -> rs = 1; Node *p = last; while(p != NULL && p -> ch[c] == NULL) { p -> ch[c] = np; p = p -> fa; } if(p == NULL) { np -> fa = rt; } else { Node *q = p -> ch[c]; if(q -> maxl == p -> maxl + 1) { np -> fa = q; } else { Node *nq = ++ tot; nq -> maxl = p -> maxl + 1; nq -> fa = q -> fa; memcpy(nq -> ch, q -> ch, sizeof(q -> ch)); q -> fa = np -> fa = nq; while(p != NULL && p -> ch[c] == q) { p -> ch[c] = nq; p = p -> fa; } } } last = np;}int first[maxn << 1];int next[maxn << 2], to[maxn << 2];int gcnt = 0;void add_edge(int u, int v) { gcnt ++; next[gcnt] = first[u]; first[u] = gcnt; to[gcnt] = v;}int len[maxn << 1], siz[maxn << 1];int F[maxn];void dfs(int x) { for(int i = first[x]; i; i = next[i]) { int v = to[i]; dfs(v); siz[x] += siz[v]; } F[len[x]] = std::max(F[len[x]], siz[x]);}int main() { static char S[maxn]; scanf("%s", S); int n = strlen(S); for(int i = 0; i < n; i ++) { extend(S[i] - 'a'); } for(int i = 0; i <= (tot - pool); i ++) { Node *p = pool + i; len[i] = p -> maxl; siz[i] = p -> rs; if(p -> fa) { int fa = (p -> fa) - pool; add_edge(fa, i); } } dfs(0); for(int i = n - 1; i >= 0; i --) { F[i] = std::max(F[i], F[i + 1]); } for(int i = 1; i <= n; i ++) { printf("%d\n", F[i]); } return 0;} |
评论 (0)
