首页 > 代码库 > POJ2774 后缀自动机&后缀数组
POJ2774 后缀自动机&后缀数组
http://poj.org/problem?id=2774
题目大意就是给两个字符串，求最长公共子串。好像可以哈希切掉，但是为了练一练后缀数组以及学一学后缀自动机，我用不同方法终于A掉了这道题。
后缀数组：就是求出height数组然后扫一遍，求出满足条件的最大值（满足条件是指height所指的两个后缀要没有公共部分），是后缀数组的水题
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 char tmp[100005],s[200005]; 6 int n,sa[200005],rak[200005],height[200005],t[200005],t2[200005],c[300]; 7 void build_sa(int m) 8 { 9 int *x=t,*y=t2,p;10 for(int i=0;i<m;i++)c[i]=0;11 for(int i=0;i<n;i++)c[x[i]=s[i]]++;12 for(int i=0;i<m;i++)c[i]+=c[i-1];13 for(int i=n-1;i>=0;i--)sa[--c[x[i]]]=i;14 for(int k=1;k<=n;k<<=1)15 {16 p=0;17 for(int i=n-k;i<n;i++)y[p++]=i;18 for(int i=0;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k;19 for(int i=0;i<m;i++)c[i]=0;20 for(int i=0;i<n;i++)c[x[y[i]]]++;21 for(int i=0;i<m;i++)c[i]+=c[i-1];22 for(int i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];23 swap(x,y);24 p=1;x[sa[0]]=0;25 for(int i=1;i<n;i++)26 x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p-1:p++;27 if(p>=n)break;28 m=p;29 }30 }31 void printsa()32 {33 puts("");34 for(int i=0;i<n;i++)35 {36 char *ss=s+sa[i];37 while(*ss)putchar(*ss++);38 puts("");39 }40 }41 void get_height()42 {43 for(int i=0;i<n;i++)rak[sa[i]]=i;44 int k=0;45 for(int i=0;i<n;i++)46 {47 if(k)k--;48 if(rak[i]==0){height[rak[i]]=k;continue;}49 int j=sa[rak[i]-1];50 while(s[i+k]==s[j+k])k++;51 height[rak[i]]=k;52 }53 }54 int main()55 {56 int mid;57 while(scanf("%s",tmp)>0)58 {59 memset(s,0,sizeof(s));60 mid=strlen(tmp);61 tmp[mid]=‘$‘;62 strcat(s,tmp);63 scanf("%s",tmp);64 tmp[strlen(tmp)+1]=‘\0‘;65 tmp[strlen(tmp)]=‘#‘;66 strcat(s,tmp);67 n=strlen(s);68 build_sa(130);69 //printsa();70 get_height();71 int ans=0;72 for(int i=1;i<n;i++)if(height[i]>ans&&((sa[i-1]<mid&&sa[i]>mid)||(sa[i-1]>mid&&sa[i]<mid)))ans=height[i];73 printf("%d\n",ans);74 }75 return 0;76 }
后缀自动机：基本上是一道模板题，用第一个字符串建好后缀自动机，再用第二个字符串匹配。。。感觉和AC自动机差不多（感觉数组写法比指针写法好看多了）
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 const int N=101000; 7 char s[N],t[N]; 8 int last,son[N<<1][30],dep[N<<1],pre[N<<1],lens,lent,tot,rt; 9 void SAM(int alp)10 {11 int u=last;dep[++tot]=dep[last]+1;12 last=tot;13 while(u&&!son[u][alp])son[u][alp]=last,u=pre[u];14 if(!u)pre[last]=rt;15 else16 {17 int v=son[u][alp];18 if(dep[v]==dep[u]+1)pre[last]=v;19 else20 {21 dep[++tot]=dep[u]+1;22 int nv=tot;23 memcpy(son[nv],son[v],sizeof(son[nv]));24 pre[nv]=pre[v];pre[v]=pre[last]=nv;25 while(u&&son[u][alp]==v)son[u][alp]=nv,u=pre[u];26 }27 }28 }29 int solve()30 {31 int cur,tmp=0,ret=0;32 cur=rt=last=++tot;33 for(int i=1;i<=lens;i++)SAM(s[i]-‘a‘);34 for(int i=1;i<=lent;i++)35 {36 if(son[cur][t[i]-‘a‘]){cur=son[cur][t[i]-‘a‘];tmp++;}37 else38 {39 while(cur&&!son[cur][t[i]-‘a‘])cur=pre[cur];40 if(!cur)cur=rt,tmp=0;41 else tmp=dep[cur]+1,cur=son[cur][t[i]-‘a‘];42 }43 ret=max(ret,tmp);44 }45 return ret;46 }47 int main()48 {49 scanf("%s%s",s+1,t+1);50 lens=strlen(s+1);lent=strlen(t+1);51 printf("%d\n",solve());52 }
POJ2774 后缀自动机&后缀数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。