[SPOJ]NSUBSTR

danihao123 posted @ 2018年3月12日 15:31 in 题解 with tags SPOJ 后缀自动机 , 98 阅读
转载请注明出处: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,然后搞个后缀最大值即可。

代码:

#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;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter