首页 > 其他分享 >后缀数组

后缀数组

时间:2024-02-14 19:22:41浏览次数:32  
标签:后缀 rank height 数组 sa 排序

后缀数组

后缀数组利用倍增思想

求出sa rank数组

然后利用这两个数组求height

最后利用height 解决一些问题

所以啥是sa rank height啊?


算法流程

定义

1.后缀数组sa

将按字典序排序后的后缀的开头位置顺次放入了sa中

换个说法就是

sa[i]表示字典序排名为i的后缀的开头的下标

2.名次数组rank

rank[i]表示以i为开头的后缀的排名

简单点说

sa[i]表示排第i的是谁

rank[i]表示i排第几

他们两个互为反函数(又是数学

3.height数组

height[i]表示sa[i]与sa[i-1]这两个(下标所代表的)后缀的最长公共前缀的长度

height数组有一些性质 一会再说


计数排序&&基数排序

在求sa之前 我们需要知道一下计数排序和基数排序

计数排序

它的工作过程分为三个步骤:

  1. 计算每个数出现了几次;
  2. 求出每个数出现次数的 前缀和
  3. 利用出现次数的前缀和,从右至左计算每个数的排名。

计数排序代码

const int N = 100010;
const int W = 100010;

int n, w, a[N], cnt[W], b[N];

void counting_sort() {
  memset(cnt, 0, sizeof(cnt));
  for (int i = 1; i <= n; ++i) ++cnt[a[i]];
  for (int i = 1; i <= w; ++i) cnt[i] += cnt[i - 1];
  for (int i = n; i >= 1; --i) b[cnt[a[i]]--] = a[i];
}

基数排序

基数排序(英语:Radix sort)是一种非比较型的排序算法,最早用于解决卡片排序的问题。

基数排序将待排序的元素拆分为k个关键字,逐一对各个关键字排序后完成对所有元素的排序。

如果关键字值域不大 就可以将计数排序作为基数排序的内核

后缀数组就是利用了以计数排序为内核的基数排序(像绕口令


倍增求后缀数组

利用前$2^{k-1}$(第一关键字) 和后$2{k-1}$(第二关键字)的rank值求当前$2k$的rank

详见代码

来源 @

时间复杂度O(n log n)

int n;
int sa[N<<1],x[N<<1],y[N<<1],cnt[N];
string s;
void GetSa()
{
	int m=128;//计数排序的值域
	memset(cnt, 0, sizeof cnt);//对原串字符计数排序,获取各字符排名
	for (int i = 1; i <= n; i++) cnt[x[i]=s[i-1]]++;//统计个数
	for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];//前缀和
	for (int i = n; i; i--) sa[cnt[x[i]]--] = i;
        //第一次计数排序结束 排完了长度为1的

	for(int k=1;k<=n;k<<=1)//倍增求SA,k为当前处理串长
	{

		int p=0;//根据上一轮求得的sa数组计算下一轮 根据第二关键字排序的顺序
		for(int i=n;i>n-k;i--) y[++p]=i;//第二关键字排序其实就是把超出串范围(即 sa[i]+w>n)的 sa[i] 放到 sa 数组头部
		for(int i=1;i<=n;i++) if(sa[i]>k) y[++p]=sa[i]-k;//然后把剩下的依原顺序放入

		memset(cnt,0,sizeof cnt);//对第一关键字进行计数排序
		for(int i=1;i<=n;i++) cnt[x[y[i]]]++;
		for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
		for(int i=n;i;i--) sa[cnt[x[y[i]]]--]=y[i];

		swap(x,y);m=0;//将 y 赋为 x 并重新计算 x(临时排名)
		for(int i=1;i<=n;i++)
			if(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) x[sa[i]]=m;
			else x[sa[i]]=++m;
		if(m==n) break;//如果已经得出m个排名即为排序完毕直接结束
	}
}

求height数组

前面说到height数组有特殊性质 现在就说(我没忘


1.对于任意前缀 j k 满足 rank[j]<rank[k]

j k 的最长公共前缀为$min_{rank[j]<i<=rank[k]} height[i]$

简单证明:

若i k j 相邻 显而易见

$LCP(i,j)=min(LCP(i,k),LCP(k,j))$

不相邻同理

2.令h[i]=height[rank[i]]

h[i]>=h[i-1]-1

这个性质保证了在O(n)的时间复杂度内求height数组

求height代码如下

void gethei()
{
	for(int i=1;i<=n;i++) rk[sa[i]]=i;//根据sa求rk数组
	for(int i=1,h=0;i<=n;hei[rk[i++]]=h)//h为前缀长度,遍历每个后缀,循环结束后h即为height
 		for(h?h--:0;s[i+h]==s[sa[rk[i]-1]+h];h++);//hei最小为上一个hei-1,然后扩展
}

到此就结束了后缀数组的过程 求出了做题用的height数组

终于写完了后缀数组 好难 撒花

标签:后缀,rank,height,数组,sa,排序
From: https://www.cnblogs.com/zysssss/p/18015480

相关文章

  • 912.排序数组--插入排序
    1.题目介绍给你一个整数数组nums,请你将该数组升序排列。示例1:输入:nums=[5,2,3,1]输出:[1,2,3,5]示例2:输入:nums=[5,1,1,2,0,0]输出:[0,0,1,1,2,5]2.题解2.1插入排序思路主要思路就是创建一个有序区域和无序区域,不断从无序区域取一张出来顺序插入有序区域即可代......
  • 912.排序数组--冒泡排序
    1.题目介绍给你一个整数数组nums,请你将该数组升序排列。示例1:输入:nums=[5,2,3,1]输出:[1,2,3,5]示例2:输入:nums=[5,1,1,2,0,0]输出:[0,0,1,1,2,5]2.题解2.1冒泡排序思路跟选择排序,固定一个i,后续者不断打擂台挑战不同,冒泡排序永远是两个邻接值比较,较大值不断向后冒......
  • 912.排序数组--选择排序
    1.题目介绍给你一个整数数组nums,请你将该数组升序排列。示例1:输入:nums=[5,2,3,1]输出:[1,2,3,5]示例2:输入:nums=[5,1,1,2,0,0]输出:[0,0,1,1,2,5]2.题解2.1插入排序思路打擂台,每次确定第一名,第二名,第三名,依次往后代码#include<bits/stdc++.h>usingnamespace......
  • leetcode——数组算法——前缀和构建和应用
    leetcode——数组算法——前缀和构建和应用前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和303.区域和检索-数组不可变比如leetcode303.区域和(检索-数组不可变)题目介绍:给定一个整数数组nums,处理以下类型的多个查询:计算索引left和right(包含left......
  • 树状数组模拟_ABC340_E - Mancala 2
    目录问题简述思路分析参考代码做题反思问题简述原题参考:E-Mancala2初始给出长度为n、m的数组a、b,要求给出m次操作后的数组a,每一次的操作流程如下:设定变量c=0;取出a[b[i]]中的数字保证手上有一个球的情况下进行以下操作:c++向a[(b[i]+c)%n]中放1可以看原题,原题有......
  • 树状数组区间修改区间查询
    树状数组区间修改区间查询问题——两种操作给定\(l,r,x\),将\([l,r]\)这个区间内的所有值都加上\(x\)给定\(l,r\)求出\([l,r]\)的区间和这道题肯定要用前缀和和差分,那么大体框架可以出来了//操作一:update(l,x),update(r+1,-x);//操作二query(r)-query(l......
  • Suffix Array:后缀数组学习笔记
    后缀排序后缀排序,顾名思义就是给后缀排个序。朴素做法是\(O(n^2\logn)\)的,无法接受。因此诞生了基于倍增思想的后缀排序算法。其中倍增思想在集训队论文中讲得很好,在此不再赘述。这里主要讲代码实现。constintN=2e6+10;chars[N];intn,m,sa[N],rk[N],tp[N],b[N];void......
  • 数状数组
    介绍树状数组主要操作为lowbit函数(取出x元素的低位二次幂)方便用于爬链操作(每层子节点通过加上低位二次幂可到达父节点),以及求前缀序列和的操作(将x减去其低位二次幂可得到前一未覆盖序列,通过累加从而达到求前缀和的操作)。点击查看代码intlowbit(intx){returnx&-x;}适用......
  • Linux 中 使用awk数组根据基因的PAV矩阵计算基因的存在频率
     001、测试数据[b20223040323@admin1test]$lsx_gather_pav.txt[b20223040323@admin1test]$catx_gather_pav.txt##测试数据;每一行是一个个体;每一列是一个基因;矩阵中的0表示基因在这个个体中缺失,1表示基因在这个个体中存在01111......
  • Linux 中 字符串 与shell数组的转换
     001、字符串转换为shell数组[root@PC1test1]#str1="aabb100200500"##生成测试字符串[root@PC1test1]#echo$str1aabb100200500[root@PC1test1]#ay1=($str1)##字符串转换为数组[root@PC1test1]#echo${ay1[0]}......