526互联

后缀数组 SA 学习笔记 （一）

发布时间 2023-09-22 23:15:19作者: hsfzbzjr

好像有一些图片炸了，慢慢修

后缀数组 SA 学习笔记 （一）

目录

目录

计数排序 Counting Sort

非比较型，稳定性

Code

    int mx=0;
    for(int i=1;i<=n;++i){
        scanf("%d",&x[i]);
        mx=max(mx,x[i]);
    }
    for(int i=1;i<=n;++i)cnt[x[i]]++;
    for(int v=1;v<=mx;++v)cnt[v]+=cnt[v-1];
    for(int i=n;i>=1;--i)y[cnt[x[i]]--]=x[i];
    //填入数值的顺序不影响正确性
    //但是倒序填写保证稳定性

cnt[v] 的含义在变化，共有三种含义：

  1. 表示 x[] 中 v 这个数值的出现次数
  2. 表示 x[] 中小于等于 v 的数值的出现次数
  3. 下一次 v 出现时所放的 y[] 中的位置

负整数的处理：

  1. 数值整体平移
  2. map

要素提炼：3 步

  1. 计数器数组
  2. 计数器前缀和
  3. 倒序定排名

桶排序 Bucket Sort

本质：值域范围分块为桶，桶内再排序

计数排序是特殊的桶排序

基数排序 Radix Sort

逐位进行多轮计数排序

非比较型，稳定性

e.g.

基数为 10

位数不足补前缀 0

Code

//基数为 10
const int B=10;
int POW[20]={1,10,100,1000,10000,100000,1000000};
int digit(int val,int p){
    return val/POW[p]%B;
}

    int mx=9;
    for(int p=0;p<=6;p++){
        memset(cnt,0,(mx+1)*sizeof(int));
        for(int i=1;i<=n;++i)key[i]=digit(x[i],p);
        for(int i=1;i<=n;++i)cnt[key[i]]++;
        for(int v=1;v<=mx;++v)cnt[v]+=cnt[v-1];
        for(int i=n;i>=1;--i)y[cnt[key[i]]--]=x[i];
        memcpy(x+1,y+1,n*sizeof(int));
    }

复杂度 : \(O(n \log R)\)

id[ ] 和 rk[ ]

id[i] 表示排序后第 i 个原来是第几个

rk[i] 代表原来第 i 个排序后是第几个

互逆关系：

id[rk[i]]=i;
rk[id[i]]=i;

e.g.

\(\rm i\) 1 2 3 4 5 6 7 8 9 10
x[i] 11 8 9 5 12 3 15 6 18 7
id[i] 6 4 8 10 2 3 1 5 7 9
rk[i] 7 5 6 2 8 1 9 3 10 4

后缀数组 Suffix Array

基础概念

对字符串所有后缀串按照字典序排序

难点：不能够显性地将所有的后缀列举出来

每个后缀串对应其开头位置

sa[r] 表示将所有后缀串排序后第 r 小的后缀的开头位置

rk[id] 表示 id 号开头的后缀串的排名

互逆关系

sa[rk[id]]=id;
rk[sa[r]]=r;

已知 sa[] 求 rk[]

e.g.

\(\rm i\) 1 2 3 4 5
sa[] 4 3 2 5 1
rk[] 5 3 2 1 4

e.g. 已知字符串 s="yxyzxyz"

求 sa[] 和 rk[]

\(\rm i\) 1 2 3 4 5 6 7
sa[] 5 2 1 6 3 7 4
rk[] 3 2 5 7 1 4 6

后缀串长度不同，末位补空字符到相同长度

计算后缀数组

基数排序+广义子串长度倍增

不断对长度为 \(2^k\) 的广义子串排序

讨论

如何想到倍增

由排序对象的特殊性，思考重复信息再利用

路径1：1 位 --> 2 位 --> 3 位 --> 4 位

路径2：1 位 --> 2 位 --> 4 位 --> 8 位

Code

    scanf("%s",s+1);
    int len=strlen(s+1);
    int mx=127;
    for(int i=1;i<=len;++i)++cnt[rk[i]=s[i]];
    for(int i=1;i<=mx;++i)cnt[i]+=cnt[i-1];
    for(int i=len;i>=1;--i)sa[cnt[rk[i]]--]=i;

之后倍增，第 k 轮前

sa[r] 表示将所有长度为 \(2^{k-1}\) 的子串排序后第 r 小的子串的开头位置

中间计算过程中，sa[] 和 rk[] 不对应后缀信息，也不满足互逆关系

	for(int shft=1;shft<len;shft<<=1){
        int j=0;
        for(int i=len;i>len-shft;--i)id[++j]=i;
        for(int r=1;r<=len;++r)
            if(sa[r]>shft)id[++j]=sa[r]-shft;  //低位关键字不需要计数排序，直接照抄上一轮的结果 
    	memset(cnt,0,(1+mx)*sizeof(int));
        for(int i=1;i<=len;++i)++cnt[key[i]=rk[id[i]]];
        for(int v=1;v<=mx;++v)cnt[v]+=cnt[v-1];
        for(int i=len;i>=1;--i)sa[cnt[key[i]]--]=id[i];   //高位关键字排序
        memcpy(rkcpy+1,rk+1,len*sizeof(int));
        int nVal=0;
        for(int r=1;r<=len;r++)
            rk[sa[r]]=eq(sa[r],sa[r-1],shft)?nVal:++nVal;
        mx=nVal;
        if(nVal<len)continue;
        for(int i=1;i<=len;i++)sa[rk[i]]=i;
        break;
    }

bool eq(int x,int y,int shft){
    return rkcpy[x]==rkcpy[y]&&
           rkcpy[x+shft]==rkcpy[y+shft];
}

讨论

数组大小： rkcpy[ ] 的大小要翻倍

复杂度：\(O(n \log n)\)

KK3299.

Description

喜欢钻研问题的JS同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法 ：把需要加密的信息排成一圈，显然，它们有很多种不同的读法。例如下图，可以读作： JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0

把它们按照字符串的大小排序：

07JSOI

7JSOI0

I07JSO

JSOI07

OI07JS

SOI07J

读出最后一列字符：I0O7SJ，就是加密后的字符串。想加密的字符串实在太长，你能写一个程序完成这个任务吗？

输入文件code.in 输入一个字符串 S 。注意字符串的内容不一定是字母、数字，也可以是符号等。保证 \(|S| \le 10^5\)

输出文件code.out 输出一个字符串。

Solution

将原字符串：断开+拉直+克隆

套用 SA 模板

将克隆串中长度大于等于原字符串长度的后缀串截掉尾部，然后做排序，再按照题意取出答案即可。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
char s[N];
int sa[N],rk[N],rkcpy[N<<1],id[N];
int key[N],cnt[N];
int len;

bool eq(int x,int y,int shft){
	return rkcpy[x]==rkcpy[y]&&
		   rkcpy[x+shft]==rkcpy[y+shft];
}

void SA(){
	int mx=127;
	for(int i=1;i<=len;i++)++cnt[rk[i]=s[i]];
	for(int i=1;i<=mx;i++)cnt[i]+=cnt[i-1];
	for(int i=len;i>=1;i--)sa[cnt[rk[i]]--]=i;
	
	for(int shft=1;shft<len;shft<<=1){
		int j=0;
		for(int i=len;i>len-shft;i--)id[++j]=i;
		for(int r=1;r<=len;r++)
			if(sa[r]>shft)id[++j]=sa[r]-shft;
		memset(cnt,0,(mx+1)*sizeof(int));
		for(int i=1;i<=len;i++)++cnt[key[i]=rk[id[i]]];
		for(int v=1;v<=mx;v++)cnt[v]+=cnt[v-1];
		for(int i=len;i>=1;i--)sa[cnt[key[i]]--]=id[i];
		memcpy(rkcpy+1,rk+1,len*sizeof(int));
		int nVal=0;
		for(int r=1;r<=len;r++)
			rk[sa[r]]=eq(sa[r],sa[r-1],shft)?nVal:++nVal;
		mx=nVal;
		if(nVal<len)continue;
		for(int i=1;i<=len;i++)
			sa[rk[i]]=i;
		break;
	} 
}

int main(){
	
	scanf("%s",s+1);
	
	int oldLen=strlen(s+1);
	len=2*oldLen;
	
	for(int i=1;i<=oldLen;i++)s[i+oldLen]=s[i];
	
	SA();
	
	for(int i=1;i<=len;i++)
		if(sa[i]<=oldLen)printf("%c",s[sa[i]+oldLen-1]);
	printf("\n");
	
//	for(int i=1;i<=len;i++)cout<<sa[i]<<" ";cout<<endl;
	
	return 0;
}