代码编织梦想

后缀数组是什么

后缀数组,SA,可用于解决字符串问题。

那我们看后缀数组:

先约束一些东西:

1.字符数组下标从1开始。
2.len表示字符数组的长度。

后缀数组主要有两个数组组成

s a [ i ] sa[i] sa[i] 表示字典序第 i i i小的后缀的开头下标 ( 1 − l e n ) (1-len) 1len

r k [ i ] rk[i] rk[i] 表示以下标为 i i i开头的后缀的字典序排名

那么显然有以下性质:

s a [ r k [ i ] ] = r k [ s a [ i ] ] = i sa[rk[i]]=rk[sa[i]]=i sa[rk[i]]=rk[sa[i]]=i

偷个图,以下即为 a a b a a a a b aabaaaab aabaaaab的后缀数组
在这里插入图片描述

如何求后缀数组?

这里的方法是 O ( l e n ∗ l o g 2 l e n ) O(len *log^2len) O(lenlog2len)

看到2个 l o g log log,是不是有想法。

很显然其中一个是交给快排的 l o g log log,那么显然另外一个就是我们算法的核心了。

那么这个 l o g log log我们就放在倍增身上吧。

作为算法的核心,我们想一下这个算法倍增的思路:

我们先考虑一下子任务:长度为1的子串的字典序排序,相当好求吧?就一个快排就出来了。

那我们用递推的思想依次完成每个子任务

1 — > 1 + 2 0 — > 1 + 2 1 — > 1 + 2 2 — > 1 + 2 3 … … 1—>1+2^0—>1+2^1—>1+2^2—>1+2^3…… 1>1+20>1+21>1+22>1+23
然后我们可以完成每个长度为 l e n len len的子串的字典序排序了

具体怎么实现呢?

我们每次对sa数组排序时取两个关键字 r k [ j ] 与 r k [ j + 2 i ] rk[j]与rk[j+2^i] rk[j]rk[j+2i]

( i 为 当 前 枚 举 的 次 幂 , j 为 排 序 的 下 标 ) (i为当前枚举的次幂,j为排序的下标) (ij)

然后我们再利用 s a sa sa数组来更新 r k rk rk数组

偷图帮助理解:
在这里插入图片描述
有图片理解应该相当轻松了吧!

CODE

LOJ模板题

码风奇怪,将就将就

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<map>
#include<bitset>
#include<queue>
#define ll long long
#define R register
#define I inline
#define N 1000005
#define mo
#define F freopen(".in","r",stdin),freopen(".out","w",stdout);
using namespace std;
int rk[N],sa[N],ork[N],len,u,now; char s[N];
I bool cmp(int x,int y) {return rk[x]==rk[y]?rk[x+u]<rk[y+u]:rk[x]<rk[y];}
I void print(int Lz) {Lz<0?putchar('-'),Lz=-Lz:Lz=Lz; if (Lz>9) print(Lz/10); putchar(Lz%10+'0');}
int main() {
	scanf("%s",s+1),len=strlen(s+1);
	for (R int i=1;i<=len;i++) sa[i]=i,rk[i]=s[i];
	for (R int i=1;i<len;i*=2) {
		u=i,sort(sa+1,sa+1+len,cmp);
		for (R int j=1;j<=len;j++) ork[j]=rk[j]; rk[sa[1]]=now=1;
		for (R int j=2;j<=len;j++) rk[sa[j]]=(ork[sa[j]]==ork[sa[j-1]]&&ork[sa[j]+u]==ork[sa[j-1]+u])?now:++now;
	} for (int i=1;i<=len;i++) print(sa[i]),putchar(' ');
}

解释以下 o r k ork ork的部分:

因为 r k rk rk数组是实时更新的,所以在更新之前我们要记录一下原数组,作为我们的比较依据。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_49972640/article/details/123296895

后缀数组学习笔记【详解|图】-爱代码爱编程

后缀数组学习笔记【详解】 老天,一个后缀数组不知道看了多少天,最后终于还是看懂了啊! 最关键的就是一会儿下标表示排名,一会用数值表示排名绕死人了。 我不知道手跑了多少次才明白过来。其实我也建议初学者手跑几遍,但是一定要注意数组的意义,否则就是无用功。 数组含义: s[ ]:输入的字符串,预处理的时候会在末尾加上一个0 sa[ ]:它的下标就是

后缀数组学习笔记_lleozhang的博客-爱代码爱编程

后缀数组是一个很迷的字符串算法... 后缀数组的特点是:思想嘛...还行 代码嘛...很乱 首先做一些基础介绍: 后缀数组(sa)是一个数组(废话),他的作用是存储字典序排名为i的后缀的位置(即后缀的起点) 而后缀数组常常与rank数组同步计算,其中rank数组是起点为i的后缀的排名 既然如此,我们只要求出sa和rank其中之一,我们就可以求出另

后缀数组的SA-IS构造方法-爱代码爱编程

SA-IS算法 之前的后缀数组都是用的倍增法来构造的,但是之前一场多校倍增的写法T了,就到网上学习了SA-IS算法,在此记录一下,长篇大论的写太耗时间了,这里就主要记录我个人的一些理解和要点以及我写全注释的代码,完整的学习博客可以参考以下几篇(在学习该算法前建议先熟悉基数排序):线性求后缀数组。诱导排序与 SA-IS 算法(该篇格式有些问题)后缀数组及S

后缀数组及lcp学习笔记-爱代码爱编程

模板题 给出一个字符串,输出排名为 i i i 的后缀的编号, i =

后缀数组学习笔记(算法进阶课)-爱代码爱编程

后缀数组学习笔记(倍增) 基础定义子串:就是字符串的一部分,必须连续。 后缀:是一种子串,它的结尾必须为字符串的最后。 大小比较:就是字典序比较,从头开始比,不相同的话字典序大的那个大,假如相同就向后移动。假如移到其中一个串的结尾还相同的话,长的那个大。 后缀数组:把所有的后缀编号,排序后把编号存在这个数组里。 名次数组:存的是每个后缀的名次 sa

字符串学习笔记2——后缀数组SA及其排序-爱代码爱编程

后缀数组和排序 上次我们讲到了前缀数组,那后缀数组又是什么呢? 首先定义后缀: 对于一个字符串 s s s,定义后缀 i

leetcode刷题笔记-1044-二分哈希/后缀数组SA/后缀自动机SAM-爱代码爱编程

题目链接:https://leetcode-cn.com/problems/longest-duplicate-substring/ 题意 给定一个字符串,求该字符串的一个出现次数大于1次的最长子串 题解 链接 解法0:二分+哈希,细节很多,不推荐使用,但思路简单,即二分答案长度,然后哈希判断是否存在重复 解法1:后缀数组,需要对height求解过

Leetcode 33. 搜索旋转排序数组(二分) 记录反思-爱代码爱编程

排序数组,目标值,logn,就差告诉我用二分了 不知道在哪里旋转,所以需要判断每次定位的位置是在旋转到前面的那部分,还是在原本的前面那部分 如何判断? 每次二分找到的中间值,可以和left 和 right 左右指针所知位置比较,比如如果nums[mid] > nums[right] ,说明[left ,mid ]是旋转到前面的那部分,然后就可

蓝桥杯 18省Ca4-第几个幸运数-爱代码爱编程

#include<bits/stdc++.h> using namespace std; // clock_t start, end; // start = clock(); // end = clock(); // cout << (double) (end - start) / CLOCKS_PER

每日一题2-爱代码爱编程

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 方法一:滑动窗口,用一个哈希表记录窗口中的元素。 class Solution { public:     int lengthOfLongestSubstring(string s) {         unordered_map<char,int> map1;

LeetCode 467. 环绕字符串中唯一的子字符串 -- 动态规划-爱代码爱编程

环绕字符串中唯一的子字符串 把字符串 s 看作是 “abcdefghijklmnopqrstuvwxyz” 的无限环绕字符串,所以 s 看起来是这样的:“…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…” . 现在给定另一个字符串 p 。返回 s 中 唯一 的 p 的 非空子串 的数量

Codeforces Round #777 (Div. 2) D. Madoka and the Best School in Russia-爱代码爱编程

课上看的题然后看错了,一直以为是要把x分成两个bea的数的乘积 prob. : def 一个数good则 它是d的倍数, 一个数bea则 它good 同时 它不能表示成2个good的数的乘积,给一个good的数x ,问这个数能否表示成两个不同的bea的数的集合的乘积 ideas : 两种做法 一个数num如果是bea的,则$d ,| ,num $