spoj 1811

1811. Longest Common Substring

Problem code: LCS

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:

题目大意:
求两个字符串的最长公共字串.输出长度.

分析:
们引入这个记号:

max：即代码中 step 变量，它表示该状态能够接受的最长的字符串长度。
min：表示该状态能够接受的最短的字符串长度。实际上等于该状态的 par 指针指向的结点的 step + 1。
max-min+1：表示该状态能够接受的不同的字符串数。

如果你很好奇这个性质为什么成立,不妨参看范浩强的博文:后缀自动机与线性构造后缀树
从后缀树的角度来思考这个问题就非常简单了.

我们先进行贪心的匹配,如果在某个点上发生失配,说明 min_x ~ max_x 之间的字符串都是不匹配的.

那么我们该如何回退呢?

这个点和parent之间的关系是: 它的parent能够接受的最长串是这个点所能接受的串的最长公共前缀.

你又非常好奇, 那么这么说吧.后缀树上parent是这个点的父节点.那么你要走到这个点,就必须经过parent.

所以我们只要沿着par边向上跳就ok了.

接下来跟KMP比较类似就不详细说了.

代码也不长:

 1 #include<cstdlib>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 const int maxn = (int)3e5, sigma = 26;
 7 char s1[maxn],s2[maxn];
 8 struct Sam{
 9     int ch[maxn][sigma],par[maxn];
10     int stp[maxn];
11     int sz,last;
12     void init(){
13         memset(ch,0,sizeof(ch)); memset(par,0,sizeof(par));    memset(stp,0,sizeof(stp));
14         sz = last = 1;
15     }
16     void ext(int c){
17         stp[++sz] = stp[last] + 1;
18         int p = last, np = sz;
19         while(!ch[p][c]) ch[p][c] = np, p = par[p];
20         if(p == 0) par[np] = 1;
21         else{
22             int q = ch[p][c];
23             if(stp[q] != stp[p] + 1){
24                 stp[++sz] = stp[p] + 1;
25                 int nq = sz;
26                 memcpy(ch[nq],ch[q],sizeof(ch[q]));
27                 par[nq] = par[q];
28                 par[q] = par[np] = nq;
29                 while(ch[p][c] == q) ch[p][c] = nq, p = par[p];
30             }
31             else par[np] = q;
32         }
33         last = np;
34     }
35     void build(char *pt){
36         int i;
37         init();
38         for(i = 0; pt[i]; ++i) ext(pt[i] - 'a');
39     }
40     int vis(char *pt){
41         int x = 1,i,ret = 0,ans = 0;
42         for(i = 0; pt[i]; ++i){
43             if(ch[x][pt[i] - 'a']) 
44                 x = ch[x][pt[i] - 'a'], ans = max(ans,++ret);
45             else x = par[x],ret = stp[x],i -= (x != 0);
46             if(x == 0) x = 1;
47         }
48         return ans;
49     }
50 }sam;
51 int main()
52 {
53     freopen("substr.in","r",stdin);
54     freopen("substr.out","w",stdout);
55     scanf("%s
",s1);
56     scanf("%s
",s2);
57     sam.build(s1);
58     printf("%d
",sam.vis(s2));
59     return 0;
60 }

View Code