SPOJ 1812 Longest Common Substring II（后缀自动机）（LCS2）

A string is finite sequence of characters over a non-empty finite set Σ.

In this problem, Σ is the set of lowercase letters.

Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string.

Now your task is a bit harder, for some given strings, find the length of the longest common substring of them.

Here common substring means a substring of two or more strings.

Input

The input contains at most 10 lines, each line consists of no more than 100000 lowercase letters, representing a string.

Output

The length of the longest common substring. If such string doesn't exist, print "0" instead.

题目大意：求多个字符串的最长公共子串。

思路：据说把多个串拼起来会MLE还是TLE？SPOJ太慢了……

给第一个串建立后缀自动机，然后把每个点的ans置为当前后缀的LCS，dp为当前某个串能匹配的最长后缀

然后每次弄完用每个点的dp更新ans……图是一个DAG……

哎呀好难说看代码吧……

代码（1500MS）：

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <cstring>
  4 using namespace std;
  5 
  6 const int MAXN = 100000 + 10;
  7 char buf[MAXN];
  8 struct State {
  9     State *fail, *go[26];
 10     int val, dp, ans;/*
 11     State() :
 12             fail(0), val(0) {
 13         memset(go, 0, sizeof go);
 14     }*/
 15 }*root, *last;
 16 State statePool[MAXN * 2], *cur;
 17 
 18 void init() {
 19     //memset(statePool, 0, 2 * strlen(buf) * sizeof(State));
 20     cur = statePool;
 21     root = last = cur++;
 22 }
 23 
 24 void extend(int w) {
 25     State *p = last, *np = cur++;
 26     np->ans = np->val = p->val + 1;
 27     while (p && !p->go[w])
 28         p->go[w] = np, p = p->fail;
 29     if (!p) np->fail = root;
 30     else {
 31         State*q = p->go[w];
 32         if (p->val + 1 == q->val) np->fail = q;
 33         else {
 34             State *nq = cur++;
 35             memcpy(nq->go, q->go, sizeof q->go);
 36             nq->ans = nq->val = p->val + 1;
 37             nq->fail = q->fail;
 38             q->fail = nq;
 39             np->fail = nq;
 40             while (p && p->go[w] == q)
 41                 p->go[w] = nq, p = p->fail;
 42         }
 43     }
 44     last = np;
 45 }
 46 
 47 inline void update_max(int &a, const int &b) {
 48     if(a < b) a = b;
 49 }
 50 
 51 inline void update_min(int &a, const int &b) {
 52     if(a > b) a = b;
 53 }
 54 
 55 struct Node {
 56     State *p;
 57     bool operator < (const Node &rhs) const {
 58         return p->val < rhs.p->val;
 59     }
 60 } a[MAXN * 2];
 61 
 62 int main() {
 63     init();
 64     scanf("%s", buf);
 65     for(char *pt = buf; *pt; ++pt)
 66         extend(*pt - 'a');
 67     int m = 0;
 68     for(State *p = statePool; p != cur; ++p) {
 69         a[m++].p = p;
 70     }
 71     sort(a, a + m);
 72     int n = 0;
 73     while(scanf("%s", buf) != EOF) {
 74         ++n;
 75         State *t = root;
 76         int l = 0;
 77         for(char *pt = buf; *pt; ++pt) {
 78             int w = *pt - 'a';
 79             if(t->go[w]) {
 80                 t = t->go[w];
 81                 update_max(t->dp, ++l);
 82             }
 83             else {
 84                 while(t && !t->go[w]) t = t->fail;
 85                 if(!t) l = 0, t = root;
 86                 else {
 87                     l = t->val;
 88                     t = t->go[w];
 89                     update_max(t->dp, ++l);
 90                 }
 91             }
 92         }
 93         for(int i = m - 1; i > 0; --i) {
 94             State *p = a[i].p;
 95             update_min(p->ans, p->dp);
 96             update_max(p->fail->dp, min(p->dp, max(p->fail->val, p->dp)));
 97             p->dp = 0;
 98         }
 99     }
100     int ans = 0;
101     for(int i = m - 1; i >= 0; --i) update_max(ans, a[i].p->ans);
102     printf("%d
", ans);
103 }

View Code