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

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