后缀数组笔记

《后缀数组笔记》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、OI笔记]后缀数组学习笔记--后缀数组解题方法总结2010-04-1507:37      后缀数组是处理字符串的有力工具。后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也并不逊色，而且它比后缀树所占用的内存空间小很多。可以说，后缀数组比后缀树要更为实用。自从拜读了罗穗骞大牛的WC2009论文《后缀数组——处理字符串的有力工具》后，经过若干星期的努力（中间有因某些原因而缓下来），终于把论文上面的练习题全部完成了，现在写写自己对后缀数组的理解和感悟

2、。在看本笔记时，请不要忘记了，这是笔记，而教材是《后缀数组——处理字符串的有力工具》。一：后缀数组的实现1、定义：SuffixArray数组（SA数组）用于保存从小到大排好序之后的后缀。RANK名次数组用来保存后缀S[i..n]在所有后缀中是第几小的后缀。简单来说，SA数组表示的是“排第几的是谁”，RANK数组表示的是“你的排名是多少”。2、求SA数组以及RANK数组的方法：详细的请转到罗穗骞大牛的论文，我的学习笔记重点不是要介绍这个。3、对DA（倍增算法）的一些个人理解：由于我只学习了倍增算法，所

3、以我只能谈谈我对它的理解。DC3算法我没有去研究....DA算法我是根据罗穗骞的模板写的，根据自己的理解做了些许的小优化。我们现在来看看罗穗骞大牛的模板：intwa[maxn],wb[maxn],wv[maxn],ws[maxn];intcmp(int*r,inta,intb,intl){returnr[a]==r[b]&&r[a+l]==r[b+l];}voidda(int*r,int*sa,intn,intm){inti,j,p,*x=wa,*y=wb,*t;for(i=0;i

4、[i]=0;for(i=0;i=0;i--)sa[--ws[x[i]]]=i;for(j=1,p=1;p=j)y[p++]=sa[i]-j;for(i=0;i

5、s[i]=0;for(i=0;i=0;i--)sa[--ws[wv[i]]]=y[i];for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i

6、量：n为字符串长度，m为字符的取值范围，r为字符串。后面的j为每次排序时子串的长度。for(i=0;i=0;i--)sa[--ws[x[i]]]=i;这四行代码，进行的是对R中长度为1的子串进行基数排序。x数组在后面需要用到，所以先复制r数组的值。特别需要注意的是，第四行的for语句，初始化语句为i=n-1，如果写得不太熟

7、练，很容易习惯性地写成i=0，我一开始就是。理解这是基数排序的最好方法，找个例子，自己推推....for(p=0,i=n-j;i=j)y[p++]=sa[i]-j;这两行代码，利用了上一次基数排序的结果，对待排序的子串的第二关键字进行了一次高效地基数排序。我们可以结合下面的图来理解：不难发现，除了第一次基数排序以外，之后的每次双关键字排序，设此次排序子串长度为j，则从第n-j位开始的子串，其第二关键字均为0，所以得到第

8、一个for语句：for(p=0,i=n-j;i