后缀数组
错误的代码。。。。 未找到原因
#include<cstdio> #include<algorithm> #include<cstring> #define maxn 110000 using namespace std; char s[maxn]; __int64 Star[maxn],End[maxn]; __int64 sa[maxn],t[maxn],t2[maxn],c[maxn],n; __int64 Rank[maxn],Height[maxn]; __int64 d[maxn][20]; __int64 idx(char ch) { return ch-'a'; } //构造字符串s的后缀数组。每个字符必须为0-m-1。 void build_sa(__int64 m) { __int64 i,*x=t,*y=t2; //基数排序 for(i=0;i<m;i++) c[i]=0; for(i=0;i<n;i++) c[x[i]=idx(s[i])]++; for(i=1;i<m;i++) c[i]+=c[i-1]; for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i; for(__int64 k=1;k<=n;k<<=1) { __int64 p=0; //直接利用sa数组排序第二关键字 for(i=n-k;i<n;i++) y[p++]=i; for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k; //基数排序第一关键字 for(i=0;i<m;i++) c[i]=0; for(i=0;i<n;i++) c[x[y[i]]]++; for(i=1;i<m;i++) c[i]+=c[i-1]; for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i]; //根据sa和y数组重新计算新的x数组 swap(x,y); p=1; x[sa[0]]=0; for(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) //以后即使继续倍增,sa也不会改变,退出 break; m=p; //下次基数排序的最大值 } } void getHeight() { __int64 i,j,k=0; for(i=0;i<n;i++) Rank[sa[i]]=i; for(i=0;i<n;i++) { if(k) k--; __int64 j=sa[Rank[i]-1]; while(s[i+k]==s[j+k] && s[i+k]!=0 ) k++; Height[Rank[i]]=k; } } void RMQ_init() { for(__int64 i=0;i<n;i++) d[i][0]=Height[i]; for(__int64 j=1;(1<<j)<=n;j++) for(__int64 i=0;i+j-1<n;i++) d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]); } __int64 RMQ(__int64 L,__int64 R) { __int64 k=0; while(1<<(k+1)<=R-L+1) k++; return min(d[L][k],d[R-(1<<k)+1][k]); } __int64 fun(__int64 x) { if(!x) return 1; __int64 cnt=0; while(x) { cnt++; x/=10; } return cnt; } int main() { __int64 i,N; __int64 ss[2]; while(scanf("%s",s)==1) { n=strlen(s); build_sa(26); getHeight(); RMQ_init(); /* printf("\nsa:\n"); for(i=0;i<n;i++) printf("%d %d\n",i,sa[i]); printf("\nrank:\n"); for(i=0;i<n;i++) printf("%d %d\n",i,Rank[i]); printf("\nheigth:\n"); for(i=0;i<n;i++) printf("%d %d\n",i,Height[i]); */ scanf("%I64d",&N); ss[0]=0; for(i=1;i<=N;i++) { scanf("%I64d%I64d",&Star[i],&End[i]); ss[0]+=End[i]-Star[i]+1; } __int64 tmp,a,b; ss[1]=End[1]-Star[1]+3; for(i=2;i<=N;i++) { if(Star[i]!=Star[i-1]) { a=min(Rank[Star[i]],Rank[Star[i-1]]); b=max(Rank[Star[i]],Rank[Star[i-1]]); tmp=RMQ(a+1,b); a=min(End[i]-Star[i],End[i-1]-Star[i-1]); tmp=min(tmp,a); } else tmp=min(End[i]-Star[i],End[i-1]-Star[i-1]); ss[1]+=End[i]-Star[i]-tmp+2; ss[1]+=fun(tmp); } printf("%I64d %I64d\n",ss[0],ss[1]); } return 0; }