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

后缀数组

时间:2024-01-28 20:57:20浏览次数:28  
标签:suf 前缀 后缀 height -- 数组 sa

后缀数组

定义

suf[i] i到最后的子串

rank[i] suf[i]在所有后缀中的排名

sa[i] 排名为 i 的后缀的开始位置

sa[i] 与 rank[i] 为互逆操作,相反的排列

height[i] suf[sa[i]] 与 suf[sa[i-1]] 的最长公共前缀

H[i] 即 Height[rank[i]]

求SA的倍增算法

用基数排序,排序次数为 \(\lceil log n \rceil\)

for(int i=1;i<=n;++i)buc[s[i]]++;
for(int i='a';i<='z';++i)buc[i] += buc[i-1];
for(int i=n;i>=1;--i)sa[buc[s[i]]--] = i;
for(int i=1;i<=n;++i)rk[sa[i]]=rk[sa[i-1]]+(s[sa[i]]!=s[sa[i-1]];)//rank初始化,相同的串相同的rk
for(int k=1;k<=n;k<<=1){//取到 log n , k 代表 1<<(k+1) 的倍增
    for(int i=1;i<=n;++i)buc[rk[sa[i]]] = i;
    for(int i=n;i>=1;--i)if(sa[i]>k)SA[buc[rk[sa[i]-k]]--]=sa[i]-k;//对rk进行基数排序 
    for(int i=n-k+1;i<=n;++i)SA[buc[rk[i]]--] = i;
    for(int i=1;i<=n;++i)RK[SA[i]]=RK[SA[i-1]]+!cmp(rk,SA[i],SA[i-1],k);
    swap(rk,RK);swap(sa,SA);
    if(rk[sa[n]]>=n)break;
}

求 height

\(H[i] \geq H[i-1]-1\)

故遍历字符串,基于 H[i-1] 来求解 H[i] 复杂度 O(n)

求两后缀的最长公共前缀(LCP)

是他们排名间的 height 的最小值,因为 sa 按字典序排序,所以最小的height后面不会有另外的字符可以构成公共前缀。

维护 height 数组上的RMQ,如st表,线段树

可重叠的重复最长字串

求两后缀的最长公共前缀,那么就是Height中的最大值

不可重叠的重复最长子串

二分答案

在height中分组,每组后缀的最大height不小于k,看里面sa的极差是否超过k,有一组即合法

标签:suf,前缀,后缀,height,--,数组,sa
From: https://www.cnblogs.com/life-of-a-libertine/p/17993316

相关文章

  • 差分数组
    构造差分数组int*constructDifferenceArray(int*nums,intlength){int*diff=(int*)malloc(length*sizeof(int));diff[0]=nums[0];for(inti=1;i<length;i++){diff[i]=nums[i]-nums[i-1];}returndiff;}通过这个diff差分数组是可以反推出原......
  • 数组前缀和
    一维数组中的前缀和https://leetcode.com/problems/range-sum-query-immutable/description/区域和检索#include<stdio.h>#include<stdlib.h>//定义NumArray结构体typedefstruct{int*preSum;//前缀和数组}NumArray;//创建NumArray对象,并计算前缀和数组......
  • Java中的数组
    数组1、数组概述数组是相同类型数据的有序集合数组描述的是相同类型的若干个数据,按照一定的先后次序排列组合而成其中,每一个数据称作一个数组元素,每个数组元素可以通过一个下标来访问它们2、数组声明创建首先必须声明数组变量,才能在程序中使用数组。下面是声明数......
  • 数组:讲解一维数组和多维数组的声明、初始化和访问。
    一维数组是最简单的数组形式,它可以存储一系列相同类型的元素。多维数组则是由多个一维数组组成的数据结构,可以用于存储多维数据。下面我将分别讲解一维数组和多维数组的声明、初始化和访问。一维数组一维数组的声明和初始化可以分为两步进行。声明一维数组在C语言中,可以使用以下语......
  • 80. 删除有序数组中的重复项 II(中)
    目录题目题解:双指针题目给你一个有序数组nums,请你原地删除重复出现的元素,使得出现次数超过两次的元素只出现两次,返回删除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。说明:为什么返回数值是整数,但输......
  • 动态区间求和——树状数组的基本应用
    目录前言问题引入思路一览具体分析前言准确来说,不应该叫做动态区间求和问题,只能说树状数组经常用于求和操作而已,但是正常的动态条件查询树状数组也是可以做的,具体的下面再说吧问题引入给出一个数组a[],要求做两种操作,一种是修改数组中的一个数,一种是实现查询区间[lt,rt](lt<=......
  • C#数组对象池ArrayPool<T>底层
    深度解析C#数组对象池ArrayPool<T>底层原理 提到池化技术,很多同学可能都不会感到陌生,因为无论是在我们的项目中,还是在学习的过程的过程,都会接触到池化技术。池化技术旨在提高资源的重复使用和系统性能,在.NET中包含以下几种常用的池化技术。(1)、连接池(Connecti......
  • 【板子】后缀自动机(SAM)
    //lg3804//Copyrightyeyou26//注意:这道题不是纯纯的后缀自动机,main函数有一点额外处理#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineN(int(2e6+6))intfa[N];intch[N][28];intlen[N];intcnt[N];llans;intidx=1;intnp=1;str......
  • 【板子】树状数组(BIT)
    //lg1908求逆序对//Copyrightyeyou26#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconstintN=(int)1e6+6;llsum;intn;structData{intorigin;intls;intid;}data[N];boolcmporigin(Datax,Datay){r......
  • 树状数组(区间修改&&区间查询)
    #include<bits/stdc++.h> #defineintlonglongusingnamespacestd;intn,m,x,x1,y,z;inta[100010],d[100010],c[100010];intlowbit(intnum){returnnum&-num;}voidadd(intx,inty){ inta=x; while(x<=n)d[x]+=y,c[x]+=(a-1)*y,x+=lowbit(x); ......