后缀数组:
先膜拜大牛: 《后缀数组——处理字符串的有力工具》 罗穗骞
我在看后缀数组的时候后看代码看了好久好久,还是木有理解透彻。求sa数组的过程可以分成四段看。第一步对呆处理字符串做预处理,即对单个字符排序。
第二步是倍增过程中的对字符串第二关键字排序过程。大牛的算法中进行了简化,用前一次的sa数组的结果直接求出第二关键字排序结果。这块我看了好久木有
看懂~~个人的理解是第二关键字排在n-j后面的都是0,因为n-j+j=n>n-1超过范围了。所以先将后面n-j到n关键字的值复制到前面,跟sa数组的值比较,得出结果。
为什么?对不对?菜鸟表示不懂……第三步是对第一关键字排序。这个过程跟第一步预处理时的排序过程一样,都是基数排序。第四步是通过所求的saz值求出
rank数组。具体理解还不是很透彻,大概是从sa的第一个开始对sa里面的值排序,一样的一个值,不一样的按字典序递增。
第二部分是求height数组部分,即求出最长公共前缀。求的过程建立在h[i]>=h[i-1]-1;然后依次求出h值。
int sa[N+10],c[N+10],wa[N+10],wb[N+10]; bool cmp(int *y,int a,int b,int l){ return y[a]==y[b]&&y[a+l]==y[b+l]; } template <class T> void suffix(T r,int n,int m){ int i,j,p,*rank=wa,*y=wb; for(i=0;i<m;i++) c[i]=0; for(i=0;i<n;i++) c[rank[i]=r[i]]++; for(i=0;i<m;i++) c[i+1]+=c[i]; for(i=n-1;i>=0;i--) sa[--c[rank[i]]]=i; for(j=1,p=1;p<n;j*=2,m=p){ for(p=0,i=n-j;i<n;i++) y[p++]=i; for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j; for(i=0;i<m;i++) c[i]=0; for(i=0;i<n;i++) c[rank[y[i]]]++; for(i=0;i<m;i++) c[i+1]+=c[i]; for(i=n-1;i>=0;i--) sa[--c[rank[y[i]]]]=y[i]; swap(rank,y); for(i=1,p=1,rank[sa[0]]=0;i<n;i++) rank[sa[i]]=cmp(y,sa[i],sa[i-1],j)?p-1:p++; } } int h[N+10]; template <class T> void height(T r,int n){ int i,j,k=0,*rank=wa; for(i=0;i<n;i++) rank[sa[i]]=i; for(i=0;i<n-1;h[rank[i++]]=k) for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++); }