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

XYP的博客

枫染红尘谁看透

 
 
 

日志

 
 

后缀数组口胡  

2016-02-14 23:10:26|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
前面还是搬罗大神论文
 基本定义
子串:字符串 S 的子串 r[i..j],i≤j,表示 r 串中从 i 到 j 这一段,
也就是顺次排列 r[i],r[i+1],...,r[j]形成的字符串。
后缀:后缀是指从某个位置 i 开始到整个串末尾结束的一个特殊子串。字
符 串 r 的 从 第 i 个 字 符 开 始 的 后 缀 表 示 为 Suffix(i) , 也 就 是
Suffix(i)=r[i..len(r)]。
大小比较:关于字符串的大小比较,是指通常所说的“字典顺序”比较,也
就是对于两个字符串 u、v,令 i 从 1 开始顺次比较 u[i]和 v[i],如果
u[i]=v[i]则令 i 加 1,否则若 u[i]<v[i]则认为 u<v,u[i]>v[i]则认为 u>v
(也就是 v<u),比较结束。如果 i>len(u)或者 i>len(v)仍比较不出结果,那
么 若 len(u)<len(v) 则 认 为 u<v , 若 len(u)=len(v) 则 认 为 u=v , 若
len(u)>len(v)则 u>v。
从字符串的大小比较的定义来看, S 的两个开头位置不同的后缀 u 和 v 进
行比较的结果不可能是相等,因为 u=v 的必要条件 len(u)=len(v)在这里不可
能满足。
后缀数组:后缀数组 SA 是一个一维数组,它保存 1..n 的某个排列 SA[1],
SA[2],……,SA[n],并且保证 Suffix(SA[i]) < Suffix(SA[i+1]),1≤i<n。
也就是将 S 的 n 个后缀从小到大进行排序之后把排好序的后缀的开头位置顺
次放入 SA 中。
名次数组:名次数组 Rank[i]保存的是 Suffix(i)在所有后缀中从小到大排
列的“名次”。
简单的说,后缀数组是“排第几的是谁?”,名次数组是“你排第几?”。容
易看出,后缀数组和名次数组为互逆运算。如图 1 所示。后缀数组口胡 - 1449097870 - XYP的博客
 设字符串的长度为 n。为了方便比较大小,可以在字符串后面添加一个字符,
这个字符没有在前面的字符中出现过,而且比前面的字符都要小。在求出名次数组后,可以仅用 O(1)的时间比较任意两个后缀的大小。在求出后缀数组或名次数组中的其中一个以后,便可以用 O(n)的时间求出另外一个。任意两个后缀如果直接比较大小,最多需要比较字符 n 次,也就是说最迟在比较第 n 个字符时一定能分出“胜负”。
1.2 倍增算法
倍增算法的主要思路是:用倍增的方法对每个字符开始的长度为 2k 的子字
符串进行排序,求出排名,即 rank 值。k 从 0 开始,每次加 1,当 2k 大于 n 以后,每个字符开始的长度为 2k 的子字符串便相当于所有的后缀。并且这些子字符串都一定已经比较出大小,即 rank 值中没有相同的值,那么此时的 rank 值就是最后的结果。每一次排序都利用上次长度为 2k-1的字符串的 rank 值,那么长度为 2k 的字符串就可以用两个长度为 2k-1的字符串的排名作为关键字表示,然后进行基数排序,便得出了长度为 2k的字符串的 rank 值。以字符串“aabaaaab”为例,整个过程如图 2 所示。其中 x、y 是表示长度为 2k的字符串的两个关键字 。后缀数组口胡 - 1449097870 - XYP的博客
 


inline void Getsa()
{
int i,j,p,m=27,*x=wa,*y=wb,*t;
for (int i=0;i<m;i++) ws[i]=0;
for (int i=0;i<n;i++) ws[x[i]=r[i]]++;
for (int i=1;i<m;i++) ws[i]+=ws[i-1];
for (int i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
//sa[]:以进入时间为第二关键字从小到大排 
for (p=1,j=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;
//fir:前半段  sec:后半段 
//y[i]:以sec排序后排名为i的fir
//x[]:当前情况下i串的排名 求y 
for (i=0;i<m;i++) ws[i]=0,wv[i]=x[y[i]];
for (i=0;i<p;i++) ws[x[i]]++;
for (i=1;i<m;i++) ws[i]+=ws[i-1];
for (i=p-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
//按fir排序,把在y中出现迟的(sec小的)在同一优先级中排后面 求sa 
for (t=x,x=y,y=t,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=(cmp(y,sa[i],sa[i-1],j))?(p-1):(p++);
//因为当两个串一样时,它们的位置也一样.要与上一个串y比较.
//sa[i]为排名为i的后缀的开头 更新x 
}
}
inline void Getheight()
{
int i,j,k=0;
for (i=0;i<n;i++) rank[sa[i]]=i;
for (i=0;i<n;h[rank[i++]]=k)
for ((k?k--:0),j=sa[rank[i]-1];r[j+k]==r[i+k];k++);
/*
h[i]=suf[sa[i]]与suf[sa[i-1]]的前缀
 
证明:h[rank[i]]>=h[rank[i-1]]-1(h[i-1]>0)
定理:suf(i)和suf(k)前缀=min(h[rank[i]+1],h[rank[i]+2]..h[rank[k]]).
设k为sa中排在值为i-1的元素(rank[i-1])前的数.(rank[k-1]==rank[i-1]-1) 
则h[i-1]为suf[k]与suf[i-1]的前缀.
k也应当会排在i前面.(rank[k]<rank[i])
如图,显然suf(i)与suf(k)前缀=suf(i-1)与suf(k-1)前缀-1.
这样,suf(i)与suf(k)的前缀=min(h[rank[k]],h[rank[k+1]]..h[rank[i]])==h[rank[i-1]]-1.
根据定理,可以发现h[rank[i]]>=suf(i)与suf(k)的前缀.
即h[rank[i]]>=h[rank[i-1]]-1.
sa[]=
k-1 orzrxd
i-1 orzrxdorz
.
.
.
k rzrxd
.
.
i rzrxdorz
*/ 
}
  评论这张
 
阅读(33)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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