Blackops

初心易得，始终难守

0%

SPOJ LCS Longest Common Substring（后缀自动机）

发表于 更新于 分类于 ， ，

LCS - Longest Common Substring
no tags
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 simple, for two 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 exactly two lines, each line consists of no more than 250000 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

Output:
3

题目链接：SPOJ LCS
后缀自动机是个好东西，把一串建立$SAM$后拿另一串去匹配，这样就可以$O(N)$地回答任意询问串与主串的最长公共子串，原理是利用了$SAM$中$fail$指向的是和当前遍历到的子串的最长公共后缀的结尾位置，随着$fail$的迭代，$len$必定越来越小，因此找到的第一个可以接下去的合法位置，就是可以接在当前失配字符后面条件下最长公共后缀子串即最优的答案。
代码：

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
#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 = 250010;
struct Trie
{
    int nxt[26], pre, len;
    void init()
    {
        pre = -1;
        len = 0;
        for (int i = 0; i < 26; ++i)
            nxt[i] = -1;
    }
} L[N << 1];
int sz, last;
char s[N], t[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 != -1 && L[t].nxt[c] == v)
            {
                L[t].nxt[c] = np;
                t = L[t].pre;
            }
        }
    }
    last = u;
}
int main(void)
{
    while (~scanf("%s", s))
    {
        init();
        scanf("%s", t);
        int ls = strlen(s), lt = strlen(t);
        for (int i = 0; i < ls; ++i)
            ins(s[i] - 'a');
        int len = 0, ans = 0;
        int u = 0;
        for (int i = 0; i < lt; ++i)
        {
            int v = t[i] - 'a';
            if(~L[u].nxt[v])
            {
                ++len;
                u = L[u].nxt[v];
            }
            else
            {
                while (~u && L[u].nxt[v] == -1)
                    u = L[u].pre;
                if(u == -1)
                {
                    u = 0;
                    len = 0;
                }
                else
                {
                    len = L[u].len + 1;
                    u = L[u].nxt[v];
                }
            }
            ans = max(ans, len);
        }
        printf("%d\n", ans);
    }
    return 0;
}