首页 > 代码库 > 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 }
spoj 1812