SPOJ1812 LCS2

发表于

  题意:给你n个串，求它们的LCS。

  后缀系列的经典问题。
  这道题用后缀数组+二分当然可以做。将n个串连接成一个长串，只需要每次二分LCP，看是否有n个后缀LCP大于该值，又正好分属n个串就好。
  但这个复杂度显然是$O(n \log n)$的，在这里过不了。我们考虑用SAM解决这个问题。
  首先我们从两个串的情况入手: (SPOJ LCS正是两串LCS的题目)
  将第一个串$s_1$的SAM构建出来，然后在上面运行第二个串$s_2$。记录一个到当前位的LCS长度，记作len。如果当前到了第i位，节点u有$s_2[i]$的转移边,则走转移边，len长度+1。如果没有该转移边，由于next边上节点所包含的串均为当前点u包含串的后缀，所以沿着next边向前走，走到第一个有该转移边的节点v。根据节点的定义，一个节点有转移边，则其中所有串均可以通过这条转移边到另一个合法子串。于是我们只需要取最长的一个。即走过v的转移边，将len重新赋值为$Max[v] + 1$。如果走到根都没有转移边的话，就从根重新开始，并将len赋值为0。每走一步更新答案即可。
  如何处理多个串的情况?我们对于每个节点多记录两个值，一个代表所有串运行到当前点时的LCS值，一个代表当前串运行到当前点时的LCS，即上面的len。注:一个串可能被运行到一个点多次，记录最大值即可。要注意的是，在之前的双串LCS中，我们忽略了一个东西:当我们运行到一个点，即代表这个点包含的串在原串出现时，该节点通过next边连接的所有点，即该串的所有后缀也都在原串出现了，所以之前的点的len值也需要更新。在两个串的情况里，运行到一个点时，其代表串的后缀显然不会更优，并不用在意这一点。但是在多串中，我们需要考虑其他串的影响，就要基数排序排出节点间的拓扑序，按照其逆序更新所有节点的真正len值。运行完一个串后，将每个节点的所有串运行到当前点的LCS值对当前len取min即可。(如果没运行到则len=0，说明该节点代表的串不会参与答案更新)
  最后运行完所有串后，所有节点LCS的max值就是答案了。
  这道题卡时间，多清空几个数组都会T。不过错误算法(不基数排序)可以水过去。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
#define rep(i, l, r) for(int i = l, i##end = r; i <= i##end; ++i)
#define drep(i, l, r) for(int i = l, i##end = r; i >= i##end; --i)
#define mp make_pair
#define ms(a, b) memset(a, b, sizeof a)
template<class T> inline bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template<class T> inline bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline T& read(T& x)
{
	static char c; bool flag = 0;
	while(!isdigit(c = getchar())) if(c == '-') flag = 1;
	for(x = c ^ 48; isdigit(c = getchar()); x = (x << 3) + (x << 1) + (c ^ 48));
	if(flag) x = -x; return x;
}
const int maxn = 100010, SIZE = maxn << 2, SIGMA = 26;
namespace SAM
{
    int ch[SIZE][SIGMA], next[SIZE], Max[SIZE];
    int LCS[SIZE], LEN[SIZE];
    int cur, last;
    void init() { cur = last = 1; }
    int New(int x) { Max[++cur] = x; return cur; }
    
    void extend(int c)
    {
        int u = New(Max[last] + 1), v = last;
        for(; v && !ch[v][c]; v = next[v]) ch[v][c] = u;
        if(!v) next[u] = 1;
        else
        {
            int h = ch[v][c];
            if(Max[h] == Max[v] + 1) next[u] = h;
            else
            {
                int o = New(Max[v] + 1);
                memcpy(ch[o], ch[h], sizeof ch[h]);
                next[o] = next[h];
                next[h] = next[u] = o;
                for(; v && ch[v][c] == h; v = next[v]) ch[v][c] = o;
            }
        }
        last = u;
    }
}
using namespace SAM;
char s[maxn];
int n, ans;
int sum[maxn], t[SIZE];
int main()
{
    init();
    scanf("%s", s); n = strlen(s);
    rep(i, 0, n - 1) extend(s[i] - 'a');
    rep(i, 1, cur) LCS[i] = Max[i];
    rep(i, 1, cur) ++sum[Max[i]];
    rep(i, 1, n) sum[i] += sum[i - 1];
    drep(i, cur, 1) t[sum[Max[i]]--] = i;
    while(~scanf("%s", s))
    {
        int h = 1, len = 0;
        ms(LEN, 0);
        rep(i, 0, strlen(s) - 1)
        {
            if(ch[h][s[i] - 'a']) ++len, h = ch[h][s[i] - 'a'];
            else
            {
                while(h && !ch[h][s[i] - 'a']) h = next[h];
                if(!h) h = 1, len = 0;
                else len = Max[h] + 1, h = ch[h][s[i] - 'a'];
            }
            chkmax(LEN[h], len);
        }
        drep(i, cur, 1) chkmax(LEN[next[t[i]]], LEN[t[i]]);
        rep(i, 1, cur) chkmin(LCS[i], LEN[i]);
    }
    rep(i, 1, cur) chkmax(ans, LCS[i]);
    printf("%d\n", ans);
    return 0;
}