后缀数组笔记.doc

OI笔记]后缀数组学习笔记--后缀数组解题方法总结 2010-04-15 07:37 ?????? 后缀数组是处理字符串的有力工具。后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也并不逊色，而且它比后缀树所占用的内存空间小很多。可以说，后缀数组比后缀树要更为实用。自从拜读了罗穗骞大牛的WC2009论文《后缀数组——处理字符串的有力工具》后，经过若干星期的努力（中间有因某些原因而缓下来），终于把论文上面的练习题全部完成了，现在写写自己对后缀数组的理解和感悟。在看本笔记时，请不要忘记了，这是笔记，而教材是《后缀数组——处理字符串的有力工具》。 一：后缀数组的实现 1、定义：Suffix Array数组（SA数组）用于保存从小到大排好序之后的后缀。RANK名次数组用来保存后缀S[i..n]在所有后缀中是第几小的后缀。简单来说，SA数组表示的是“排第几的是谁”，RANK数组表示的是“你的排名是多少”。 2、求SA数组以及RANK数组的方法：详细的请转到罗穗骞大牛的论文，我的学习笔记重点不是要介绍这个。 3、对DA（倍增算法）的一些个人理解：由于我只学习了倍增算法，所以我只能谈谈我对它的理解。DC3算法我没有去研究.... DA算法我是根据罗穗骞的模板写的，根据自己的理解做了些许的小优化。我们现在来看看罗穗骞大牛的模板： int wa[maxn],wb[maxn],wv[maxn],ws[maxn];int cmp(int *r,int a,int b,int l){return r[a]==r[b]r[a+l]==r[b+l];}void da(int *r,int *sa,int n,int m){int i,j,p,*x=wa,*y=wb,*t;for(i=0;im;i++) ws[i]=0;for(i=0;in;i++) ws[x[i]=r[i]]++;for(i=1;im;i++) ws[i]+=ws[i-1];for(i=n-1;i=0;i--) sa[--ws[x[i]]]=i;for(j=1,p=1;pn;j*=2,m=p){for(p=0,i=n-j;in;i++) y[p++]=i;for(i=0;in;i++) if(sa[i]=j) y[p++]=sa[i]-j;for(i=0;in;i++) wv[i]=x[y[i]];for(i=0;im;i++) ws[i]=0;for(i=0;in;i++) ws[wv[i]]++;for(i=1;im;i++) ws[i]+=ws[i-1];for(i=n-1;i=0;i--) sa[--ws[wv[i]]]=y[i];for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;in;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;}return;} 其实，我个人认为，对于这个算法以及代码，无需过分深入地理解，只需记忆即可，理解只是为了帮助记忆罢了。先解释变量：n为字符串长度，m为字符的取值范围，r为字符串。后面的j为每次排序时子串的长度。 for(i=0;im;i++) ws[i]=0;for(i=0;in;i++) ws[x[i]=r[i]]++;for(i=1;im;i++) ws[i]+=ws[i-1];for(i=n-1;i=0;i--) sa[--ws[x[i]]]=i; 这四行代码，进行的是对R中长度为1的子串进行基数排序。x数组在后面需要用到，所以先复制r数组的值。特别需要注意的是，第四行的for语句，初始化语句为i=n-1，如果写得不太熟练，很容易习惯性地写成i=0，我一开始就是。理解这是基数排序的最好方法，找个例子，自己推推.... for(p=0,i=n-j;in;i++) y[p++]=i;for(i=0;in;i++) if(sa[i]=j) y[p++]=sa[i]-j; 这两行代码，利用了上一次基数排序的结果，对待排序的子串的第二关键字进行了一次高效地基数排序。我们可以结合下面的图来理解： 不难发现，除了第一次基数排序以外，之后的每次双关键字排序，设此次排序子串长度为j，则从第n-j位开始的子串，其第二关键字均为0，所以得到第一个for语句：for(p=0,i=n-j;in;i++) y[p++]=i;使用pascal的朋友们注意了，这里之所以是n-j位，是因为c++的字符串是从第0位开始表示的。这里，p暂时成为了一个计数变量。第二个语句的意义，分析上图也不难理解，这里留给朋友们你们自行思考啦。（不如说我懒...） for(i=0;in;i++) wv[i]=x[y[i]];for(