第一次做了一道有一定难度的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;
}

• 相关文章
• 全局相关文章