震惊！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;
}

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