首页 > 代码库 > hdu 4691 Front compression (后缀数组)
hdu 4691 Front compression (后缀数组)
题目大意:
介绍了一种压缩文本的方式,问压缩前后的文本长度。
思路分析:
后缀数组跑模板然后考虑两次l r之间的lcp。
然后减掉重复的长度。
注意ans2的累加。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <cmath> #define maxn 200005 using namespace std; typedef long long ll; char str[maxn]; int sa[maxn],t1[maxn],t2[maxn],c[maxn],n; void suffix(int m) { int *x=t1,*y=t2; for(int i=0; i<m; i++)c[i]=0; for(int i=0; i<n; i++)c[x[i]=str[i]]++; for(int i=1; i<m; i++)c[i]+=c[i-1]; for(int i=n-1; i>=0; i--)sa[--c[x[i]]]=i; for(int k=1; k<=n; k<<=1) { int p=0; for(int i=n-k; i<n; i++)y[p++]=i; for(int i=0; i<n; i++)if(sa[i]>=k)y[p++]=sa[i]-k; for(int i=0; i<m; i++)c[i]=0; for(int i=0; i<n; i++)c[x[y[i]]]++; for(int i=0; i<m; i++)c[i]+=c[i-1]; for(int i=n-1; i>=0; i--)sa[--c[x[y[i]]]]=y[i]; swap(x,y); p=1; x[sa[0]]=0; for(int i=1; i<n; i++) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++; if(p>=n)break; m=p; } } int rank[maxn],height[maxn]; int RMQ[maxn]; int mm[maxn]; int best[30][maxn]; void getheight() { int k=0; for(int i=0; i<n; i++)rank[sa[i]]=i; for(int i=0; i<n; i++) { if(k)k--; if(!rank[i])continue; int j=sa[rank[i]-1]; while(str[i+k]==str[j+k])k++; height[rank[i]]=k; } } void initRMQ() { mm[0]=-1; for(int i=1; i<=n; i++) mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1]; for(int i=1; i<=n; i++)best[0][i]=i; for(int i=1; i<=mm[n]; i++) for(int j=1; j+(1<<i)-1<=n; j++) { int a=best[i-1][j]; int b=best[i-1][j+(1<<(i-1))]; if(RMQ[a]<RMQ[b])best[i][j]=a; else best[i][j]=b; } } int askRMQ(int a,int b) { int t; t=mm[b-a+1]; b-=(1<<t)-1; a=best[t][a]; b=best[t][b]; return RMQ[a]<RMQ[b]?a:b; } int Lcp(int a,int b) { a=rank[a]; b=rank[b]; if(a>b)swap(a,b); return height[askRMQ(a+1,b)]; } int Count(int x) { if(x==0)return 1; int res=0; while(x) { res++; x/=10; } return res; } int L[maxn],R[maxn]; int main() { while(scanf("%s",str)!=EOF) { n=strlen(str)+1; suffix(128); getheight(); for(int i=1;i<=n;i++)RMQ[i]=height[i]; initRMQ(); int cas; scanf("%d",&cas); ll ans1=0,ans2=0; for(int i=0;i<cas;i++) { scanf("%d%d",&L[i],&R[i]); if(i==0) { ans1+=R[i]-L[i]+1; ans2+=R[i]-L[i]+3; continue; } int tmp; if(L[i]!=L[i-1])tmp = Lcp(L[i-1],L[i]); else tmp=1000000; tmp = min(tmp,min(R[i]-L[i],R[i-1]-L[i-1])); ans1+=(R[i]-L[i]+1); ans2+=R[i]-L[i]-tmp+1; ans2++; ans2+=Count(tmp); } printf("%I64d %I64d\n",ans1,ans2); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。