SPOJ Longest Common Substring

LCS - 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

Added by:	Bin Jin
Date:	2007-09-24
Time limit:	0.294s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel Pentium G860 3GHz)
Languages:	All except: C++ 5

解题：SAM求LCS

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 251000;
 4 struct SAM{
 5     struct node{
 6         int son[26],f,len;
 7         void init(){
 8             f = -1;
 9             len = 0;
10             memset(son,-1,sizeof son);
11         }
12     }sn[maxn<<1];
13     int tot,last;
14     void init(){
15         tot = last = 0;
16         sn[tot++].init();
17     }
18     int newnode(){
19         sn[tot].init();
20         return tot++;
21     }
22     void extend(int c){
23         int np = newnode(),p = last;
24         sn[np].len = sn[p].len + 1;
25         while(p != -1 && sn[p].son[c] == -1){
26             sn[p].son[c] = np;
27             p = sn[p].f;
28         }
29         if(p == -1) sn[np].f = 0;
30         else{
31             int q = sn[p].son[c];
32             if(sn[p].len + 1 == sn[q].len) sn[np].f = q;
33             else{
34                 int nq = newnode();
35                 sn[nq] = sn[q];
36                 sn[nq].len = sn[p].len + 1;
37                 sn[q].f = sn[np].f = nq;
38                 while(p != -1 && sn[p].son[c] == q){
39                     sn[p].son[c] = nq;
40                     p = sn[p].f;
41                 }
42             }
43         }
44         last = np;
45     }
46 }sam;
47 char sa[maxn],sb[maxn];
48 int main(){
49     while(~scanf("%s%s",sa,sb)){
50         sam.init();
51         int len1 = strlen(sa);
52         int len2 = strlen(sb);
53         for(int i = 0; i < len1; ++i)
54             sam.extend(sa[i]-'a');
55         int p = 0,ret = 0,clen = 0;
56         for(int i = 0; i < len2; ++i){
57             int k = sb[i] - 'a';
58             if(sam.sn[p].son[k] != -1){
59                 clen++;
60                 p = sam.sn[p].son[k];
61             }else{
62                while(p != -1 && sam.sn[p].son[k] == -1) p = sam.sn[p].f;
63                 if(p == -1) clen = p = 0;
64                 else{
65                     clen = sam.sn[p].len + 1;
66                     p = sam.sn[p].son[k];
67                 }
68             }
69             ret = max(ret,clen);
70         }
71         printf("%d
",ret);
72     }
73     return 0;
74 }

View Code