[SPOJ]LCS2

danihao123 posted @ 2018年3月19日 17:04 in 题解 with tags SPOJ 后缀自动机 , 711 阅读
转载请注明出处:http://danihao123.is-programmer.com/

和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;
}
NSE holidays 说:
Aug 04, 2022 01:49:12 AM

National Stock Exchange has got some specific timing, during which the trading will be scheduled and later there will not be an official trading session processed. There will be no trading possessed during the Saturday and Sunday along with some National Holidays declared by the Indian Government, and if anyone is trading, then they must be aware of these NSE holiday list. NSE holidays National Stock Exchange is open from Monday to Friday during the business hours to operate share market trading.There will be no trading possessed during the Saturday and Sunday along with some National Holidays declared by the Indian Government, and if anyone is trading, then they must be aware of these NSE holiday list.

CGBSE Model Paper Cl 说:
Sep 09, 2022 07:03:41 PM

Chhattisgarh Board of Secondary Education, Raipur Board subject experts and other private school teaching staff have designed and suggested the CG Board 8th Class Model Paper 2023 with sample answers Set wide as SET-A, SET-B, SET-C and SET-D to know the new exam scheme or question pattern. CGBSE Model Paper Class 8 Every Secondary Level 8th Grade Student of the state can download the CGBSE STD-8 Question Paper 2023 Pdf along with the class teacher suggesting all lesson or chapter’s most important questions and practice with revisions and Mock Test for All Languages and Subjects to score top marks in all exams held in Term1 & Term2.


登录 *


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