Blackops

初心易得，始终难守

0%

SPOJ LCS2 Longest Common Substring II（后缀自动机+parent树）

发表于 分类于 ， ，

LCS2 - Longest Common Substring II
suffix-array-8
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.

Example

Input:
alsdfkjfjkdsal
fdjskalajfkdsla
aaaajfaaaa

Output:
2
Notice: new testcases added

题目链接：SPOJ LCS2
跟$LCSI$很像的做法，每一个节点记录${第i个串在此匹配到的最长长度}$，然后对每一个节点再记录$min{第i个串在此匹配到的最长长度}$其中的最小值（因为只有最小值才能满足所有串）。所有节点的最小值组成的集合中的最大值就是答案了，当然由于$fail$指向的子串是以当前节点结尾子串的后缀，因此如果$L[i].sumlen$存在，那么$L[L[i].fail].sumlen$完全可以达到$L[i].sumlen$的长度，但是由于肯定不能超过自身的最长长度，因此在传递的时候也要按条件更新一下：

代码：

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 100010;
struct Trie
{
    int nxt[26], pre, len, Min, sum;
    void init()
    {
        for (int i = 0; i < 26; ++i)
            nxt[i] = -1;
        pre = -1;
        len = 0;
        Min = INF, sum = 0;
    }
} L[N << 1];
int sz, last, x[N << 1], cnt[N];
char s[N];

void init()
{
    sz = last = 0;
    L[sz++].init();
}
inline int newnode()
{
    L[sz].init();
    return sz++;
}
void ins(int c)
{
    int u = newnode();
    L[u].len = L[last].len + 1;
    int t = last;
    while (~t && L[t].nxt[c] == -1)
    {
        L[t].nxt[c] = u;
        t = L[t].pre;
    }
    if (t == -1)
        L[u].pre = 0;
    else
    {
        int v = L[t].nxt[c];
        if (L[t].len + 1 == L[v].len)
            L[u].pre = v;
        else
        {
            int np = newnode();
            L[np] = L[v];
            L[np].len = L[t].len + 1;
            L[u].pre = L[v].pre = np;
            while (~t && L[t].nxt[c] == v)
            {
                L[t].nxt[c] = np;
                t = L[t].pre;
            }
        }
    }
    last = u;
}
int main(void)
{
    init();
    int len, i;
    scanf("%s", s);
    len = strlen(s);
    for (i = 0; i < len; ++i)
        ins(s[i] - 'a');
    for (i = 0; i < sz; ++i)
        ++cnt[L[i].len];
    for (i = 1; i <= len; ++i)
        cnt[i] += cnt[i - 1];
    for (i = sz - 1; i >= 0; --i)
        x[--cnt[L[i].len]] = i;
    while (~scanf("%s", s))
    {
        int len = strlen(s);
        int u = 0;
        int l = 0;
        for (i = 0; i < sz; ++i)
            L[i].sum = 0;
        for (i = 0; i < len; ++i)
        {
            int c = s[i] - 'a';
            if (~L[u].nxt[c])
            {
                ++l;
                u = L[u].nxt[c];
            }
            else
            {
                while (~u && L[u].nxt[c] == -1)
                    u = L[u].pre;
                if (u == -1)
                    u = l = 0;
                else
                {
                    l = L[u].len + 1;
                    u = L[u].nxt[c];
                }
            }
            L[u].sum = max(L[u].sum, l);
        }
        for (i = sz - 1; i >= 1; --i)
        {
            int u = x[i], pre = L[u].pre;
            L[pre].sum = min(L[pre].len, max(L[pre].sum, L[u].sum));
        }
        for (i = 0; i < sz; ++i)
            L[i].Min = min(L[i].Min, L[i].sum);
    }
    int ans = 0;
    for (i = 0; i < sz; ++i)
        ans = max(ans, L[i].Min);
    printf("%d\n", ans);
    return 0;
}