SPOJ 1811 Longest Common Substring

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


题解：
哈哈很意外啊，在电脑城随便找台机子用洛谷在线IDE 1A这题啊
讲讲思路:
以A建立SAM 让B在SAM上匹配
可以类比于kmp思想，我们知道在Parent树上，fa是当前节点的子集，也就是说满足最大前缀，利用这个就可以做题了
步骤如下：
1.如果满足ch[p][c]存在，那么就直接走就是了，和AC自动机类似，len++
2.如果不存在，那么就沿fa上跳，找到最大dis[fa]且满足存在c这个儿子的.类似于跳fail链
3.跳到根就直接初始化，重新开始

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cmath>
 6 using namespace std;
 7 const int N=550005;
 8 char S[N];int n=0,cnt=1,cur=1,last=1,ch[N][26],fa[N],dis[N];
 9 void build(int c){
10     last=cur;cur=++cnt;dis[cur]=++n;
11     int p=last;
12     for(;p && !ch[p][c];p=fa[p])ch[p][c]=cur;
13     if(!p)fa[cur]=1;
14     else{
15         int q=ch[p][c];
16         if(dis[q]==dis[p]+1)fa[cur]=q;
17         else{
18             int nt=++cnt;dis[nt]=dis[p]+1;
19             memcpy(ch[nt],ch[q],sizeof(ch[q]));
20             fa[nt]=fa[q];fa[q]=fa[cur]=nt;
21             for(;ch[p][c]==q;p=fa[p])ch[p][c]=nt;
22         }
23     }
24 }
25 int ans=0;
26 void Flr()
27 {
28     int p=1,nxt,lt;
29     scanf("%s",S);
30     int l=strlen(S),len=0,c;
31     for(int i=0;i<l;i++){
32         c=S[i]-'a';
33         if(ch[p][c]){
34             len++;p=ch[p][c];
35         }
36         else{
37             lt=0;nxt=0;
38             while(p!=1){
39                 if(ch[p][c] && dis[p]>lt)lt=dis[p],nxt=p;
40                 p=fa[p];
41             }
42             if(nxt)
43             p=ch[nxt][c],len=dis[nxt]+1;
44             else
45             p=1,len=0;
46         }
47         if(len>ans)ans=len;
48     }
49     printf("%d
",ans);
50 }
51 void work()
52 {
53     scanf("%s",S);
54     for(int i=0,l=strlen(S);i<l;i++)build(S[i]-'a');
55     Flr();
56 }
57 int main()
58 {
59     work();
60     return 0;
61 }