倍增算法,时间复杂度O(nlogn)
sa从小到大保存相对大小的下标
理解LSD,x数组,sa数组
char s[maxn];
int sa[maxn],t[maxn],t2[maxn],c[maxn],n; void build_sa(int m)
{
//LSD基数排序
int *x=t,*y=t2;//x数组保存rank
//字串长度为1,即对每一个元素的大小排序
for(int i=0;i<m;++i) c[i]=0;//计数数组清空
for(int i=0;i<n;++i) c[x[i]=s[i]]++;//统计出现次数
for(int i=1;i<m;++i) c[i]+=c[i-1];//计算前缀和
for(int i=n-1;i>=0;--i) sa[--c[x[i]]]=i;//sa从小到大保存每一个元素的下标 for(int k=1;k<=n;k<<=1){//k为要排序的子串长 //排序第二keyword
int p=0; //y[]从小到大保存第二keyword的下标
for(int i=n-k;i<n;++i) y[p++]=i;//从第n-k位開始的字串,第二keyword为0
for(int i=0;i<n;++i) if(sa[i]>=k) y[p++]=sa[i]-k;
//仅仅有下标大于k的第sa[i]个字符串的rank才干作为下一行的第sa[i]-k个字符串的第二keyword //排序第一keyword
//x[y[i]]是引用第一keyword,依据LSD第二次排序要在第一次的基础上
for(int i=0;i<m;++i) c[i]=0;//计数数组清空
for(int i=0;i<n;++i) c[x[y[i]]]++;//统计rank出现次数
for(int i=1;i<m;++i) c[i]+=c[i-1];//求前缀和
for(int i=n-1;i>=0;--i) sa[--c[x[y[i]]]]=y[i];//sa[]从小到大保存双keyword的下标 p=1;swap(x,y);x[sa[0]]=0;//交换x,y数组 x[]数组从0到n-1保存rank值(0到p)
for(int i=1;i<n;++i){
x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k] ? p-1:p++;//注意p-1
//因为p是计数rank值不同的字符串的数量,因此双keyword同样的串视为一样的rank
} if(p>=n) break; //p个字符串的rank值都不同 ,p>=n时说明大小确立,以后即使倍增,sa也不会改变
m=p;//用来下次基数排序的最大值
}
}
————————————————————————————————————--————————
————————————————————————————————————————————
void build_sa()
{
int *x=t,*y=t2;
for(int i=0;i<m;++i) c[i]=0;
for(int i=0;i<n;++i) c[x[i]=y[i]]++;
for(int i=1;i<m;++i) c[i]+=c[i-1];
for(int i=n-1;i>=0;--i) sa[--c[x[i]]]=i; for(int k=1;k<=n;k<<=1){
int p=0;
for(int i=n-k;i<n;++i) y[p++]=i;
for(int i=0;i<n;++i) if(sa[i]>=k) y[p++]=sa[i]-k; for(int i=0;i<m;++i) c[i]=0;
for(int i=0;i<n;++i) c[x[y[i]]]++;
for(int i=1;i<m;++i) c[i]+=c[i-1];
for(int i=n-1;i>=0;--i) sa[--c[x[y[i]]]]=y[i]; int p=0;swap(x,y);x[sa[0]]=0;
for(int i=1;i<n;++i){
x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k] p-1:p++;
}
if(p>=n) break;
m=p; }
}
int m;
int cmp_suffix(char *pattern,int p)
{
return strncmp(pattern,s+sa[p],m);
} int find(char *p)
{
m=strlen(p);
if(cmp_suffix(p,0)<0) return -1;
if(cmp_suffix(p,n-1)>0) return -1;
int l=0,r=n-1;
while(l<=r){
int mid=l+(r-l)/2;
int res=cmp_suffix(p,mid);
if(!res) return mid;
if(res>0) l=mid+1;
if(res<0) r=mid-1;
}
return -1;
} /*
设suffix(k)是排在suffix(i-1)前一名的后缀。则它们的最长公共前缀是h[i-1] 。那么suffix(k+1)将排在suffix(i)的前面(这里要求h[i-1]>1,假设h[i-1]≤ 1,原式显然成立)而且suffix(k+1)和suffix(i)的最长公共前缀是h[i-1]-1, 所以suffix(i)和在它前一名的后缀的最长公共前缀至少是h[i-1]-1。依照h[1] ,h[2],……,h[n]的顺序计算。并利用h数组的性质,时间复杂度能够降为O (n)。 */
void get_height()
{
for(int i=0;i<n;++i) rank[sa[i]]=i;
int k=0;
for(int i=0;i<n;++i){
if(k) k--;
int j=sa[rank[i]]-1;
while(s[j+k]==s[i+k]) k++;
height[rank[i]]=k;
}
}
后缀数组suffix array的更多相关文章
-
后缀数组(suffix array)
参考: Suffix array - Wiki 后缀数组(suffix array)详解 6.3 Suffix Arrays - 算法红宝书 Suffix Array 后缀数组 基本概念 应用:字 ...
-
后缀数组(suffix array)详解
写在前面 在字符串处理当中,后缀树和后缀数组都是非常有力的工具. 其中后缀树大家了解得比较多,关于后缀数组则很少见于国内的资料. 其实后缀数组是后缀树的一个非常精巧的替代品,它比后缀树容易编程实现, ...
-
利用后缀数组(suffix array)求最长公共子串(longest common substring)
摘要:本文讨论了最长公共子串的的相关算法的时间复杂度,然后在后缀数组的基础上提出了一个时间复杂度为o(n^2*logn),空间复杂度为o(n)的算法.该算法虽然不及动态规划和后缀树算法的复杂度低,但其 ...
-
数据结构之后缀数组suffix array
在字符串处理当中,后缀树和后缀数组都是非常有力的工具,其中后缀树大家了解得比较多,关于后缀数组则很少见于国内的资料.其实后缀是后缀树的一个非常精巧的替代品,它比后缀树容易编程实现,能够实现后缀树的很多 ...
-
后缀数组 (Suffix Array) 学习笔记
\(\\\) 定义 介绍一些写法和数组的含义,首先要知道 字典序 . \(len\):字符串长度 \(s\):字符串数组,我们的字符串存储在 \(s[0]...s[len-1]\) 中. \(suff ...
-
【模板】BZOJ 1692:队列变换—后缀数组 Suffix Array
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1692 题意: 给出一个长度为N的字符串,每次可以从串头或串尾取一个字符,添加到新串中,使新串 ...
-
笔试算法题(40):后缀数组 &; 后缀树(Suffix Array &; Suffix Tree)
议题:后缀数组(Suffix Array) 分析: 后缀树和后缀数组都是处理字符串的有效工具,前者较为常见,但后者更容易编程实现,空间耗用更少:后缀数组可用于解决最长公共子串问题,多模式匹配问题,最长 ...
-
suffix array后缀数组
倍增算法 基本定义子串:字符串 S 的子串 r[i..j],i≤j,表示 r 串中从 i 到 j 这一段也就是顺次排列 r[i],r[i+1],...,r[j]形成的字符串. 后缀:后缀是指从某个位置 ...
-
Suffix Array 后缀数组
后缀数组 顾名思义.SuffixArray(下面有时简称SA) 和字符串的后缀有关. 后缀:字符串中某个位置一直到结尾的子串.(SA中讨论包含了原串和空串).所以共同拥有len+1个后缀. 后缀数组: ...
随机推荐
-
深入理解IoC/DI
------------------------------------------------------------------------ 理解IoC/DI 1.控制反转 --> 谁控制谁 ...
-
oracle常用系统表
转自:http://blog.chinaunix.net/uid-200142-id-3479306.html dba_开头..... dba_users 数据库用户信息 dba_segme ...
-
在Mac上使用vim的几个命令
Mac上面编辑文件的命令总是记不住,留一个参考!!! 如果是vim,则:Esc 退出编辑模式,输入以下命令: :wq 保存后退出vi,若为 :wq! 则为强制储存后退出(常用) :w 保存但不 ...
-
IOS常用正则表达式
IOS常用正则表达式 正则表达式用于字符串处理.表单验证等场合,实用高效.现将一些常用的表达式收集于此,以备不时之需. 匹配中文字符的正则表达式: [\u4e00-\u9fa5] 评注:匹配中文还真是 ...
-
System.Windows.Media.Imageing.BItmapImage 这么用才不会占用文件
// Read byte[] from png file BinaryReader binReader = new BinaryReader(File.Open(filepath, FileMode. ...
-
使用CollectionView做横向滑动分页效果:
一开始几页滑动是没有问题的,等滑到三四个页面之后,就出现奇怪的缝隙,一开始死活找不到原因,最后在layout的代理方法minimumLineSpacingForSectionAtIndex返回值设置为 ...
-
Docker简介和安装
1.Docker 和传统虚拟化方式的不同之处 传统虚拟机技术是虚拟出一套硬件后,在其上运行一个完整操作系统,在该系统上再运行所需应用进程: 而容器内的应用进程直接运行于宿主的内核,容器内没有自己的内核 ...
-
Springboot配置文件解析器
@EnableScheduling @MapperScan(value = "com.****.dao") @EnableTransactionManagement @Enable ...
-
DOM 基础
文档对象模型(Document Object Model)是表示和处理一个HTML或XML文档的常用方法 查找 直接查找 var obj = document.getElementById('i1') ...
-
一文带你学会使用YOLO及Opencv完成图像及视频流目标检测(上)|附源码
计算机视觉领域中,目标检测一直是工业应用上比较热门且成熟的应用领域,比如人脸识别.行人检测等,国内的旷视科技.商汤科技等公司在该领域占据行业领先地位.相对于图像分类任务而言,目标检测会更加复杂一些,不 ...