danihao123's Blog

复习SAM了呢~

那个度数为1的点至多有20个的条件非常神奇……让我们想想怎么用。

我们发现，（钦定根后）在树上有一条路径是弯的这种情况非常不好统计，但如果是直着下来就很好说（把所有从根到一个点的路径扔到SAM里，然后是经典题）。但是，任何一条路一定会在某个度数为1的点为根的情况下是直的（可以意会一下吧（逃

然后我们从那20个点每个点当根DFS一遍，把搞出来的每一条从根开始的路径放前缀Trie里。然后对前缀Trie构一个SAM就行啦~

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <vector>
const int BUFSIZE = 128 * 1024 * 1024;
char buf[BUFSIZE];
void *alloc(size_t size) {
  static char *cur = buf;
  if(cur - buf + size > BUFSIZE) {
    return malloc(size);
  } else {
    char *ret = cur; cur += size;
    return ret;
  }
}

const int maxn = 100005;
std::vector<int> G[maxn];
int deg[maxn];

int ssiz;
struct TNode {
  TNode *ch[10];
};
TNode *alloc_tn() {
  auto ret = (TNode*)alloc(sizeof(TNode));
  memset(ret -> ch, 0, sizeof(ret -> ch));
  return ret;
}
TNode *step(TNode *o, int c) {
  if(!(o -> ch[c])) {
    o -> ch[c] = alloc_tn();
  }
  return (o -> ch[c]);
}
TNode *trt;
int col[maxn];
void dfs(int x, int fa, TNode *last) {
  TNode *np = step(last, col[x]);
  for(auto v : G[x]) {
    if(v != fa) {
      dfs(v, x, np);
    }
  }
}

struct Node {
  int len; Node *fa;
  Node *ch[10];
};
std::vector<Node*> pool;
Node *alloc_node(int len = 0, Node *fa = NULL) {
  Node *ret = (Node*)alloc(sizeof(Node));
  ret -> len = len; ret -> fa = fa;
  memset(ret -> ch, 0, sizeof(ret -> ch));
  pool.push_back(ret);
  return ret;
}
Node *rt;
Node *extend(int c, Node *last) {
  Node *np = alloc_node(last -> len + 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 -> len == p -> len + 1) {
      np -> fa = q;
    } else {
      Node *nq = alloc_node(p -> len + 1, 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;
      }
    }
  }
  return np;
}
void dfs_2(TNode *o, Node *last) {
  for(int i = 0; i < ssiz; i ++) {
    TNode *v = o -> ch[i];
    if(!v) continue;
    Node *np = extend(i, last);
    dfs_2(v, np);
  }
}

using ll = long long;
int main() {
  int n; scanf("%d%d", &n, &ssiz);
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &col[i]);
  }
  trt = alloc_tn();
  for(int i = 1; i <= n - 1; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    G[u].push_back(v); G[v].push_back(u);
    deg[u] ++; deg[v] ++;
  }
  for(int i = 1; i <= n; i ++) {
    if(deg[i] == 1) {
      dfs(i, 0, trt);
    }
  }
  rt = alloc_node();
  dfs_2(trt, rt);
  ll ans = 0;
  for(auto p : pool) {
    if(p -> fa) {
      ans += p -> len - p -> fa -> len;
    }
  }
  printf("%lld\n", ans);
  return 0;
}

和LCS那题很像，但是现在有十个串了……

还是考虑构建一个串的SAM。然后考虑SAM上每个点，剩余若干个串都可能会覆盖一下这个点，我们要取最短的那个。

然后我们就直接把其他几个串都在SAM上跑一遍（方法类似于LCS）就行了，并且注意每个点对自己的祖先也是有贡献的。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <unordered_set>
const int maxn = 100005;
const int INF = 0x3f3f3f3f;
const int maxno = maxn << 1;
struct Node {
  Node *fa; int len; int ans[12];
  Node *ch[26];
  Node *lc, *rb;
};
Node pool[maxno];
Node *rt, *last;
Node *cnt;
void init_pool() {
  rt = last = cnt = pool;
  rt -> fa = NULL; rt -> len = 0;
  rt -> ans[0] = 0;
  // memset(rt -> ans, 0, sizeof(rt -> ans));
}
Node *alloc_node(int len = 0, Node *fa = NULL) {
  Node *ret = ++ cnt;
  ret -> len = len; ret -> fa = fa;
  // memset(ret -> ans, 0, sizeof(ret -> ans));
  ret -> ans[0] = len;
  return ret;
}

int idx(char c) {
  return c - 'a';
}
void insert(char cc) {
  int c = idx(cc);
  Node *np = alloc_node(last -> len + 1);
  Node *p = last;
  while(p != NULL && p -> ch[c] == NULL) {
    p -> ch[c] = np;
    p = p -> fa;
  }
  if(!p) {
    np -> fa = rt;
  } else {
    Node *q = p -> ch[c];
    if(q -> len == p -> len + 1) {
      np -> fa = q;
    } else {
      Node *nq = alloc_node(p -> len + 1, 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;
}
void dfs(int id, Node *u) {
  for(Node *c = u -> lc; c; c = c -> rb) {
    dfs(id, c);
    u -> ans[id] = std::max(u -> ans[id], c -> ans[id]);
  }
}
void run(int id, char *S) {
  int n = strlen(S);
  Node *u = rt;
  int len = 0;
  for(int i = 0; i < n; i ++) {
    int c = idx(S[i]);
    if(u -> ch[c]) {
      len ++; u = u -> ch[c];
    } else {
      Node *p = u;
      while(p != NULL && p -> ch[c] == NULL) p = p -> fa;
      if(p == NULL) {
        len = 0; u = rt;
      } else {
        len = p -> len + 1; u = p -> ch[c];
      }
    }
    u -> ans[id] = std::max(u -> ans[id], len);
  }
  dfs(id, rt);
}
int tot = 0;
int dfs_2(Node *u) {
  int ans = *std::min_element(u -> ans, u -> ans + tot + 1);
  for(Node *c = u -> lc; c; c = c -> rb) {
    ans = std::max(ans, dfs_2(c));
  }
  return ans;
}

int main() {
  static char buf[maxn];
  scanf("%s", buf);
  init_pool();
  int n = strlen(buf);
  for(int i = 0; i < n; i ++) {
    insert(buf[i]);
  }
  for(int i = 1; i <= (cnt - pool); i ++) {
    Node *u = pool + i;
    Node *f = u -> fa;
    u -> rb = f -> lc;
    f -> lc = u;
  }
  while(scanf("%s", buf) == 1) {
#ifdef LOCAL
    if(buf[0] == '-') break;
#endif
    run(++ tot, buf);
    // memset(buf, 0, sizeof(buf));
  }
  printf("%d\n", dfs_2(rt));
  return 0;
}

xjbYY了一下竟然就艹过去了……

如果说是我们知道了每个点出发能得到的串有多少个，我们就能用类似树上求\(k\)大的求法来搞了。问题来了，怎么知道这个？

我先说一下不重复的情况吧，首先到达这个点就有一种串了，然后我们加上他的出边（注意是转移边！）指向的点的值就行了。重复的情况我们考虑一下\(|Right(x)|\)就能搞出来了

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <utility>
#include <queue>
#include <algorithm>
#include <set>
const int maxn = 500005;
const int maxno = maxn * 4;
const int bufsiz = 50 * 1024 * 1024;
typedef long long ll;

int fa[maxno], ch[maxno][26];
int len[maxno];
ll ans[maxno][2], val[maxno];
int rt, last;
int cur;
inline void init_sam() {
  rt = last = 1;
  cur = 1;
  ans[1][0] = ans[1][1] = -1LL;
}
inline int alloc_node(int l = 0, int f = 0) {
  int ret = ++ cur;
  len[ret] = l; fa[ret] = f;
  ans[ret][0] = ans[ret][1] = -1LL;
  return ret;
}
inline int idx(char c) {
  return c - 'a';
}
inline void extend(char cx) {
  int c = idx(cx);
  int np = alloc_node(len[last] + 1);
  val[np] = 1LL;
  int p = last;
  while(p && !(ch[p][c])) ch[p][c] = np, p = fa[p];
  if(!p) {
    fa[np] = rt;
  } else {
    int q = ch[p][c];
    if(len[q] == len[p] + 1) {
      fa[np] = q;
    } else {
      int nq = alloc_node(len[p] + 1, fa[q]);
      memcpy(ch[nq], ch[q], sizeof(ch[q]));
      fa[q] = fa[np] = nq;
      while(p && ch[p][c] == q) ch[p][c] = nq, p = fa[p];
    }
  }
  last = np;
}
int lc[maxno], rb[maxno];
inline void add_edge(int c, int f) {
  rb[c] = lc[f];
  lc[f] = c;
}
void dfs_1(int x) {
  for(int i = lc[x]; i; i = rb[i]) {
    dfs_1(i);
    val[x] += val[i];
  }
}
void dfs_2(int x) {
  if(ans[x][0] != -1LL) return;
  ans[x][0] = 1LL; ans[x][1] = val[x];
  for(int c = 0; c < 26; c ++) {
    int v = ch[x][c];
    if(v) {
      dfs_2(v);
      ans[x][0] += ans[v][0];
      ans[x][1] += ans[v][1];
    }
  }
}
inline void process() {
  for(int i = 2; i <= cur; i ++) {
    add_edge(i, fa[i]);
  }
  dfs_1(1); dfs_2(1);
#ifdef LOCAL
  for(int i = 1; i <= cur; i ++) {
    printf("ans[%d] : (%lld, %lld)\n", i, ans[i][0], ans[i][1]);
  }
#endif
}
char ret[maxno];
void search(ll k, int typ) {
  static ll val_0[maxno];
  for(int i = 1; i <= cur; i ++) {
    val_0[i] = 1;
  }
  ll *self[2] = {val_0, val};
  k += self[typ][1];
  if(k > ans[1][typ]) {
    ret[0] = '-', ret[1] = '1';
    return;
  }
  int cnt = 0;
  int u = 1;
  while(k > self[typ][u]) {
    int used = 0;
    k -= self[typ][u];
    for(int c = 0; c < 26; c ++) {
      int v = ch[u][c];
      if(!v) continue;
      used ++;
      if(k > ans[v][typ]) {
        k -= ans[v][typ];
      } else {
        ret[cnt ++] = c + 'a';
#ifdef LOCAL
        printf("Towardsing %d with %c\n", v, c + 'a');
        printf("k : %lld\n", k);
#endif
        u = v; break;
      }
    }
    // if(used == 0) break;
  }
}

int main() {
  static char S[maxn];
  scanf("%s", S); int n = strlen(S);
  int typ; ll k; scanf("%d%lld", &typ, &k);
  init_sam();
  for(int i = 0; i < n; i ++) {
    extend(S[i]);
  }
  process();
  search(k, typ);
  puts(ret);
  return 0;
}

震惊！SAM与AC自动机间的神秘关系，竟然是为了……

考虑到是子串嘛，我们建立\(A\)的后缀自动机，考虑把\(B\)放在上面进行匹配。然后考虑当前节点下面再加一个字符，如果有这个字符的转移那么直接走过去即可。如果没有呢？

观察到SAM上的父亲其实就是一个被儿子包含了的子串，所以这一步走不下去，可以考虑去找父亲解决。所以找到最低的有该转移的祖先，转移过去即可。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
const int maxn = 250005;
const int maxsiz = 30000005;
char buf[maxsiz];
char *cur = buf;
void *alloc(size_t size) {
  if(cur - buf + size > maxsiz) {
    return malloc(size);
  } else {
    void *ret = (void*)cur;
    cur += size;
    return ret;
  }
}

int idx(char c) {
  return c - 'a';
}
struct Node {
  Node *fa;
  int len;
  Node *ch[26];
};
Node *alloc_node(int len = 0, Node *fa = NULL) {
  Node *ret = (Node*)alloc(sizeof(Node));
  ret -> len = len; ret -> fa = fa;
  memset(ret -> ch, 0, sizeof(ret -> ch));
  return ret;
}
Node *rt, *last;
void init_sam() {
  rt = alloc_node();
  last = rt;
}
void extend(char c) {
  int i = idx(c);
  Node *np = alloc_node(last -> len + 1);
  Node *p = last;
  while(p != NULL && p -> ch[i] == NULL) {
    p -> ch[i] = np;
    p = p -> fa;
  }
  if(p == NULL) {
    np -> fa = rt;
  } else {
    Node *q = p -> ch[i];
    if(q -> len == p -> len + 1) {
      np -> fa = q;
    } else {
      Node *nq = alloc_node(p -> len + 1, q -> fa);
      memcpy(nq -> ch, q -> ch, sizeof(q -> ch));
      np -> fa = q -> fa = nq;
      while(p != NULL && p -> ch[i] == q) {
        p -> ch[i] = nq;
        p = p -> fa;
      }
    }
  }
  last = np;
}

char A[maxn], B[maxn];
int search() {
  int n = strlen(B);
  Node *u = rt;
  int ans = 0, len = 0;
  for(int i = 0; i < n; i ++) {
    int c = idx(B[i]);
    if(u -> ch[c]) {
      u = u -> ch[c];
      len ++;
    } else {
      while(u != NULL && u -> ch[c] == NULL) u = u -> fa;
      if(u == NULL) {
        u = rt; len = 0;
      } else {
        len = u -> len + 1;
        u = u -> ch[c];
      }
    }
    ans = std::max(ans, len);
  }
  return ans;
}

int main() {
  scanf("%s%s", A, B);
  int n = strlen(A);
  init_sam();
  for(int i = 0; i < n; i ++) {
    extend(A[i]);
  }
  printf("%d\n", search());
  return 0;
}

辣鸡爆炸OJ又被卡了说好的修bug呢说好的新OJ呢哼我去loj交了

本题的正解是SA，但很显然可以用SAM搞过去（逃

首先字符集过大？我们可以考虑开map解决转移的问题。

然后思考一个点加入后对答案会有什么影响。一个点的对答案的贡献，就是他自己的最大表示范围减去他父亲的。因为更小的长度在之前都已经被表示过了。即使之后这个点被拆成了两个，那这两个点对答案的总贡献是不会变的。所以每次加完点，把贡献加到答案里即可。

代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
typedef long long ll;
#define REP(i, l, r) for(int i = (l); i <= (r); i ++)
struct Node {
  Node *fa;
  std::map<int, Node*> *ch;
  int len;
  Node() {
    fa = NULL;
    ch = new std::map<int, Node*>();
  }
  Node(int l) {
    fa = NULL;
    ch = new std::map<int, Node*>();
    len = l;
  }
  ~Node() {
    delete ch;
  }
};
Node *rt, *last;
void init() {
  rt = new Node(0);
  // rt -> tl = 1;
  last = rt;
}
ll ans = 0;
void insert(int c) {
  static int clk = 1;
  Node *np = new Node();
  np -> len = last -> len + 1;
  Node *p = last;
  while(p != NULL && p -> ch -> count(c) == 0) {
    p -> ch -> insert(std::make_pair(c, np));
    p = p -> fa;
  }
  if(p == NULL) {
    np -> fa = rt;
  } else {
    Node *q = (*(p -> ch -> find(c))).second;
    if(q -> len == p -> len + 1) {
      np -> fa = q;
    } else {
      Node *nq = new Node(p -> len + 1);
      nq -> fa = q -> fa;
      nq -> ch -> insert(q -> ch -> begin(), q -> ch -> end());
      // nq -> ch -> insert(std::make_pair(c, np));
      np -> fa = q -> fa = nq;
      while(p != NULL && ((*(p -> ch -> find(c))).second) == q) {
        p -> ch -> erase(p -> ch -> find(c));
        p -> ch -> insert(std::make_pair(c, nq));
        p = p -> fa;
      }
    }
  }
  last = np;
  ans += np -> len - np -> fa -> len;
}
 
int main() {
  int n; scanf("%d", &n);
  init();
  REP(i, 1, n) {
    int c; scanf("%d", &c);
    insert(c);
    printf("%lld\n", ans);
  }
  return 0;
}

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