注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

一个蒟蒻的代码回收站

最后一次省选求rp

 
 
 

日志

 
 

后缀系列专题之一:后缀数组  

2014-08-15 16:03:00|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

后缀数组是后缀树(关于后缀树什么的后面会讲,后面不会讲了,为啥不用sam建后缀树呢)的一个简单的替代品,时间效率高,代码简单,易于理解。(其实主要是代码简单,易于理解……时间效率还是后缀树&&后缀自动机高)


后缀数组sa[i]表示,将s[i]的所有后缀排序之后排名为i的后缀是从哪位开始的(排第i的是谁)。

有了后缀数组,我们就可以在后缀数组中进行二分了。

给出代码(这段来自刘汝佳的白书):

int find(char *P)
{
m=strlen(P);
if (cmp_suffix(P,0)<0) return -1;//cmp_suffix(P,x)为比较字符串P是否为后缀x的前缀。
if (cmp_suffix(P,n-1)>0) return -1;
int l=0,r=n-1;
while (r>=l)
{
int mid=l+(r-l)/2;
int res=cmp_suffix(P,mid);
if (!res) return mid;
if (res<0) r=mid-1;else l=mid+1;
}
return -1;
}

现在的问题是:我们如何求出SA数组。

一个可行的办法是:对每个后缀进行排序。

但是这样的时间复杂度是O(n^2logn)的。这样的复杂度显然不能接受。

下面介绍一个Manber和Myers发明的倍增算法。它只要nlogn的复杂度


首先,将所有单个字符(对所有后缀的第一个字母排序)排序,计算出每个字母的rank。

然后给长度为2的子串排序(对所有后缀的前两个字母排序)。

再对长度为4的子串排序(因为我们已经拍过了两个字符的,所以长度为4的两个子串比较=比较他们的前两个字符+比较他们的后两个字符,所以我们只要对一个二元组排序即可,并不用对整个字符串排序)

最后排到所有rank各不相同,程序结束。

大约是这样的一个图:(图片来自nocow)

后缀系列专题之一:后缀数组 - mxh1999 - 一个蒟蒻的代码回收站
 

 这样只要进行logn次的排序,每次排序只需要O(n)的时间(基数排序,如果是快拍则是nlogn),所以时间复杂度是O(nlogn)的。

代码:(非常好写,才12个for)

void build_sa(int m)
{
int i,*x=t,*y=t2;
for (i=0;i<m;i++) c[i]=0;
for (i=0;i<n;i++) c[x[i]=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 (int k=1;k<=n;k*=2)
{
int p=0;
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=0;i<m;i++) c[i]+=c[i-1];
for (i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
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) break;
m=p;
}
}

但是,只有SA这东西用处还不是很大……

我们有一个更加强大的东西——height数组!

再此之前,我们先定义一个辅助的rank数组:rank[i]表示后缀i在SA里的排名是多少(i排第几)

height[i]表示rank为i的后缀和rank为i-1的后缀的最长公共前缀(LCP)(也可以是跟rank为i+1的LCP,不要在意这些细节)

如何求出height数组?

我们还是先考虑暴力算法:每次取两个字符串暴力找LCP。复杂度是O(n^2)的。这样当然是非常蛋疼的……

如何优化?

我们考虑一下后缀之间的联系……

我们知道,每个后缀减掉第一个字母就变成另外一个后缀了。

然后我们会发现一个性质height[rank[i]]>=height[rank[i-1]]-1;

证明?我不会……(Ruchiose:“OI竞赛不需要证明!”)

我们可以感性的理解一下,大约是长这样的一个东西(图是用画图画的求轻喷QAQ):

后缀系列专题之一:后缀数组 - mxh1999 - 一个蒟蒻的代码回收站
 

 其中红色部分为一个字母;

那么浅蓝色部分也是相同的。

所以height[rank[i]]>=height[rank[i-1]]-1;

这样我们就可以O(n)求height了。

代码:

void build_height()
{
int i,j,k=0;
for (i=0;i<n;i++) rank[sa[i]]=i;
for (i=0;i<n;i++)
{
if (rank[i]==0) continue;
if (k) k--;
int j=sa[rank[i]-1];
while (s[i+k]==s[j+k]) k++;
height[rank[i]]=k;
}
}

有了height,我们求任意两个后缀的LCP=求一次区间最小值。

然后RMQ可以搞到O(nlogn)或O(n);

这样可以把多模板匹配从O(mlogn)搞成O(m+logn)。(lrj:具体应该怎么做,请读者思考,当然我不会这么坑啦~)

详情见2009年国家集训队罗穗骞的论文《后缀数组——处理字符串的有力工具》

呼啦啦~口胡完啦~

  评论这张
 
阅读(20)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018