「CODEVS3160」最长公共子串
题目描述 Description
给出两个由小写字母组成的字符串，求它们的最长公共子串的长度。
输入描述 Input Description
读入两个字符串
输出描述 Output Description
输出最长公共子串的长度
样例输入 Sample Input
|
1 2 |
yeshowmuchiloveyoumydearmotherreallyicannotbelieveit yeaphowmuchiloveyoumydearmother |
样例输出 Sample Output
27
数据范围及提示 Data Size & Hint
单个字符串的长度不超过100000
题解
算法1：后缀数组
同poj2774
bzoj挂了没事干。。。
2014.9.21 *1
2015.2.6 *1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<map> #include<cmath> #define inf 1000000000 #define pa pair<int,int> #define ll long long using namespace std; int n,p,q,k,ans,mid; int v[200005],a[200005],h[200005]; int sa[2][200005],rk[2][200005]; char ch[200005]; void calsa(int *sa,int *rk,int *SA,int *RK) { for(int i=1;i<=n;i++) v[rk[sa[i]]]=i; for(int i=n;i;i--) if(sa[i]>k) SA[v[rk[sa[i]-k]]--]=sa[i]-k; for(int i=n-k+1;i<=n;i++) SA[v[rk[i]]--]=i; for(int i=1;i<=n;i++) RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i]+k]!=rk[SA[i-1]+k]); } void getsa() { p=0,q=1; for(int i=1;i<=n;i++)v[a[i]]++; for(int i=1;i<=30;i++)v[i]+=v[i-1]; for(int i=1;i<=n;i++) sa[p][v[a[i]]--]=i; for(int i=1;i<=n;i++) rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i]]!=a[sa[p][i-1]]); for(k=1;k<n;k<<=1,swap(p,q)) calsa(sa[p],rk[p],sa[q],rk[q]); } void geth() { k=0; for(int i=1;i<=n;i++) if(rk[p][i]==1)h[rk[p][i]]=0; else { int j=sa[p][rk[p][i]-1]; while(a[i+k]==a[j+k])k++; h[rk[p][i]]=k;if(k>0)k--; } } bool jud(int x) { int mn,mx; for(int i=1;i<=n;i++) { if(h[i]<x)mn=inf,mx=0; mn=min(mn,sa[p][i]); mx=max(mx,sa[p][i]); if(mn<mid&&mx>mid)return 1; } return 0; } int main() { scanf("%s",ch+1); mid=strlen(ch+1); ch[++mid]='z'+1; scanf("%s",ch+mid+1); n=strlen(ch+1); for(int i=1;i<=n;i++)a[i]=ch[i]-'a'+1; getsa(); geth(); int l=0,r=100000; while(l<=r) { int x=(l+r)>>1; if(jud(x))ans=x,l=x+1; else r=x-1; } printf("%d\n",ans); return 0; } |
算法2：后缀自动机
将第一个串建sam后第二个串在上面匹配QAQ
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<map> #include<cmath> #define eps 1e-6 #define inf 1000000000 #define mod 1000000007 #define pa pair<int,int> #define ll long long using namespace std; ll read() { ll x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int ans; char ch[100005]; struct sam{ int p,q,np,nq; int cnt,last; int a[200005][26],l[200005],fa[200005]; sam(){ last=++cnt; } void extend(int c){ p=last;np=last=++cnt;l[np]=l[p]+1; while(!a[p][c]&&p)a[p][c]=np,p=fa[p]; if(!p)fa[np]=1; else { q=a[p][c]; if(l[p]+1==l[q])fa[np]=q; else { nq=++cnt;l[nq]=l[p]+1; memcpy(a[nq],a[q],sizeof(a[q])); fa[nq]=fa[q]; fa[np]=fa[q]=nq; while(a[p][c]==q)a[p][c]=nq,p=fa[p]; } } } void build(){ scanf("%s",ch+1); int len=strlen(ch+1); for(int i=1;i<=len;i++) extend(ch[i]-'a'); } void solve(){ scanf("%s",ch+1); int len=strlen(ch+1),now=1,tmp=0; for(int i=1;i<=len;i++) { int c=ch[i]-'a'; if(a[p][c])p=a[p][c],tmp++; else { while(p&&!a[p][c])p=fa[p]; if(!p)p=1,tmp=0; else tmp=l[p]+1,p=a[p][c]; } ans=max(ans,tmp); } printf("%d\n",ans); } }sam; int main() { sam.build(); sam.solve(); return 0; } |
计数器 9813828
OI 课件=>
OI 课件=>
for(int i=n;i>=0;i–) if(sa[i]>k) SA[v[rk[sa[i]-k]]–]=sa[i]-k;
这句是什么意思,求解释
这个我怎么解释。。。你看看论文？
v记录之前的每一个rank最后出现的位置。。然后你从后往前枚举，对每个相同的前半部分，一定先找到后半部分最大的。。然后他就应该放在当前最大的位置。。
看到09年论文貌似懂了。。
是后缀自动机快还是DC3快→_→
论文上说有一个奇怪的不用二分的方法，打了之后发现wa了三个，求解释