首页 > 代码库 > spoj 1812

spoj 1812

1812. Longest Common Substring II

Problem code: LCS2

 

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

大意:

求出多个串的最长公共字串,输出长度.

 

分析:

我们这么想:

我们先拿两个串A,B匹配,然后在两个串的匹配过程中计算出后缀自动机SAM_A中某个节点x能在B中匹配的最长的长度.

那么这个问题就解决了.(我可以继续匹配C,D)最后取个min.

裸地解决这个问题是O(L2)的.

所以我们应用上spoj1811中的性质: parent _x 和 x 节点的最长公共部分是 max_parent_x.

那么我们只要利用孩子的匹配长度就能够直接推出parent的匹配长度. min(Min[par[x]], Max[x])

(Min[x] 表示从x节点开始在当前已经考虑的串中,从x节点出发能够拓展的最长的长度. Max[x] 表示在当前串内, 从x节点出发, 能够匹配的最长的长度.)

值得注意的是,当 Min[par[x]] != 0 && Max[x] != 0 时, Min[par[x]] + 1 <= Max[x].

所以,我们现在的关键在于面对 Max[x] == 0 的情况.

这种情况下,表明从x这个点无法进行拓展,所以自然表示par[x] 也无法进行拓展,因为par是x的极大后缀串.

 所以我们迭代更新Min的值,最后取Min就ok了.

代码中加入了一个特判来验证我的猜想:

偷懒没有用"鸡排"....见谅.

技术分享
 1 #include<cstdlib> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cassert> 6 using namespace std; 7 const int maxn = (int)1.01e6,sigma = 26; 8 char str[maxn]; 9 int Min[maxn * 2],Max[maxn * 2],id[maxn * 2];10 int cmq(int,int);11 struct Sam{12     int ch[maxn * 2][sigma],par[maxn * 2],stp[maxn * 2];13     int sz,last;14     void init(){15         sz = last = 1;16     }17     void ext(int c){18         stp[++sz] = stp[last] + 1;19         int p = last, np = sz;20         for(; !ch[p][c]; p = par[p]) ch[p][c] = np;21         if(p == 0) par[np] = 1;22         else{23             int q = ch[p][c];24             if(stp[q] != stp[p] + 1){25                 stp[++sz] = stp[p] + 1;26                 int nq = sz;27                 memcpy(ch[nq],ch[q],sizeof(ch[q]));28                 par[nq] = par[q];29                 par[q] = par[np] = nq;30                 for(; ch[p][c] == q; p = par[p]) ch[p][c] = nq;31             }32             else par[np] = q;33         }34         last = np;35     }36     void ins(char *pt){37         int i;38         init();39         for(i = 0; pt[i]; ++i) ext(pt[i] - a);40     }41     void prep(){42         int i;43         for(i = 1; i <= sz; ++i) Min[i] = stp[i];44         for(i = 1; i <= sz; ++i) id[i] = i;45         sort(id + 1, id + sz + 1,cmq); 46     }47     void cmp(char *pt){48         int i,x = 1,cnt = 0;49         fill(Max, Max + sz + 2, 0);50         for(i = 0; pt[i]; ++i){51             if(ch[x][pt[i] - a]){52                 x = ch[x][pt[i] - a];53                 Max[x] = max(Max[x],++cnt);54             }55             else{56                 while(x != 1 && !ch[x][pt[i] - a]) x = par[x], cnt = stp[x];57                 if(ch[x][pt[i] - a]) x = ch[x][pt[i] - a],Max[x] = max(Max[x],++cnt);58             }59         }        60         for(i = 1; i <= sz; ++i){61             if(id[i] != 1 && Min[par[id[i]]] && Max[id[i]])62                 assert(Min[par[id[i]]] + 1 <= Max[id[i]]);63             Min[id[i]] = min(Min[id[i]], Max[id[i]]);            64             Max[par[id[i]]] = max(Max[par[id[i]]], Max[id[i]]);65         }66     }67 }sam;68 int cmq(int x,int y){69     return sam.stp[x] > sam.stp[y];70 }71 int main()72 {73     freopen("substr.in","r",stdin);74     freopen("substr.out","w",stdout);75     scanf("%s",str);76     sam.ins(str);77     sam.prep();78     while(scanf("%s",str) != EOF) 79         sam.cmp(str);80     printf("%d\n",*max_element(Min + 1, Min + sam.sz + 1));81     return 0;82 }
View Code

 

spoj 1812