正文

后缀数组

cdcq（本博客废弃！现用博客：https://www.cn  cdcq（本博客废弃！现用博客：https://www.cnblogs.com/cdcq/）  2022-08-02  608

关键词：

先说后缀是啥：后缀就是一个串s从第s[i]一直到串尾就是这个串的一个后缀，记作suffix[i]

举个栗子：aacbds的后缀分别为aacbds,acbds,cbds,ds,ds,s（这是回音你懂吗是回音你懂吗回音你懂吗音你懂吗你懂吗懂吗吗）

后缀数组实质就是给每个后缀排个序

比如上面内个串（aacbds，不是回音内个），它的后缀数组就是{1,2,4,3,5,6}

把每个后缀一个一个拿出来排太慢，会T掉，这个时候就要用到强大的倍增算法

倍增求后缀数组：

本质就是从1开始倍增一个l，把rank[i]和rank[i+l]看做是一个长度为2的串（如果i+l>=n呢么rank[i+l]=0），给这个长度为2的串排下序，在根据这次拍的序继续倍增然后继续排

为什么呐，因为字符串排序是从前往后优先级逐渐递减，内个长度为2的串就相当于把一个串拆卡，拆开的部分的名次前面已经求出来了（因为倍增的长度依次*2，所以从中间拆两半拆出来的名次前面一定求过），而且内个长度为2的串是个串，所以优先级也是前面的大（如果看不懂可以自己画下图，或者直接看内个超级经典的图（基本上有关后缀数组的教程都有内个图，是国家集训队论文的图））

排内个长度为2的串一般用桶排序，非常方便

下面是加上注释的代码，我的代码缩行了，而且用了一些省略的写法，看不懂的同学可以去网上搜索其它版本的代码

 1 int n;  char s[1100];
 2 int rank[1100],height[1100];
 3 int cnt[1100],cnt_rank[1100];//桶
 4 int rank1[1100],rank2[1100];//要拼成长度为2的串的两个名次
 5 int SA[1100],temp_SA[1100];//表示rank[i]是从下标为几的字符开始的
 6 void get_suffix_rank(){
 7     memset(cnt,0,sizeof(cnt));
 8     for(int i=0;i<n;i++)  cnt[s[i]]++;//计数
 9     for(int i=1;i<=210;i++)  cnt[i]+=cnt[i-1];//把名次堆起来
10     //因为这个版本的名次是堆的，所以a,a,b,b,c的名次分别是1,1,3,3,4
11     for(int i=0;i<n;i++)  rank[i]=cnt[s[i]]-1;//因为搞了个'$'所以要-1让'$'的名次为0
12     for(int l=1;l<n;l*=2){//倍增长度
13         for(int i=0;i<n;i++){  rank1[i]=rank[i];  rank2[i]=(i+l<n) ? rank[i+l] : 0;}//两个名次拼成一个长度为2的串
14         //下面是基数排序，因为长度为2所以直接分成两个写
15         memset(cnt_rank,0,sizeof(cnt_rank));
16         for(int i=0;i<n;i++)  cnt_rank[rank2[i]]++;
17         for(int i=1;i<n;i++)  cnt_rank[i]+=cnt_rank[i-1];
18         for(int i=n-1;i>=0;i--)  temp_SA[--cnt_rank[rank2[i]]]=i;//注意这里是n-1到0
19         memset(cnt_rank,0,sizeof(cnt_rank));
20         for(int i=0;i<n;i++)  cnt_rank[rank1[i]]++;
21         for(int i=1;i<n;i++)  cnt_rank[i]+=cnt_rank[i-1];
22         for(int i=n-1;i>=0;i--)  SA[--cnt_rank[rank1[temp_SA[i]]]]=temp_SA[i];//和上一个相比就是把i换成了temp_SA
23         rank[SA[0]]=0;
24         for(int i=1;i<n;i++){
25             rank[SA[i]]=rank[SA[i-1]];
26             rank[SA[i]]+=(rank1[SA[i]]!=rank1[SA[i-1]] || rank2[SA[i]]!=rank2[SA[i-1]]);
27         }
28     }
29 }
30 
31 int main(){//freopen("ddd.in","r",stdin);
32     scanf("%s",&s);  n=strlen(s);  s[n++]='$';//最后要搞个这个东西，防止在倍增过程中出现重复的（比如说a要比a$小）

View Code

还有一种叫做DC3的算法，复杂度更优，然而我并不会一。一，有兴趣的同学可以去网上搜索，在OI里倍增一般够用了，而且倍增简单得多

然而只是求出后缀数组一般没什么卵用，更多的时候要用到一个叫做height的非常强大的数组

height里面存的是相邻两个后缀的LCP，即最长公共前缀

怎么求呐：

你也可以把每相邻两个后缀从头比较，不会酱紫太慢，会T掉

可以像kmp那样搞，根据前面求出来的height直接跳过不用对比的地方，直接从上一个height开始比

怎么证明我太弱不会，如果哪天我懂了会来补上去

这是代码：

1 void get_height(){
2     int _l=0;
3     for(int i=0;i<n;i++)if(rank[i]){
4         int j=SA[rank[i]-1];
5         while(i+_l<n && j+_l<n && s[i+_l]==s[j+_l])  _l++;
6         height[rank[i]]=_l;
7         _l-=(_l>0);//因为往后推了一位，所以要-1
8     }
9 }

View Code

后缀数组还有很多很棒的应用，这个会另开一篇

刚学后缀数组的时候会觉得很难，然而多看几遍，照着标程写的同时一步一步理解，时间长了后缀数组就和线段树一样不过是随手写出来的小工具而已

后缀数组记录(代码片段)

后缀数组参考:彻底弄懂后缀数组后缀数组——处理字符串的有力工具知乎以洛谷P3809【模板】后缀排序为例，看了两天才理解了七成的数据结构┭┮﹏┭┮。先上经典图后缀数组是一个搞出字符串所有后缀的一个字典序排名。字... 查看详情

初识后缀数组

...荐博客：https://www.cnblogs.com/zinthos/p/3899725.html 所谓的后缀数组，就是将字符串的n个后缀全部取出来，采用字典序的排序方式，将排序好的后缀开头位置顺次放进数组中。在后缀数组中，有几个关键的变量1.SA数组，若sa[i]=j,所... 查看详情

后缀数组(suffixarray)

参考：Suffixarray-Wiki后缀数组(suffixarray)详解6.3 SuffixArrays-算法红宝书SuffixArray后缀数组基本概念应用：字符串处理、生物信息序列处理后缀：学过英语的都知道什么叫后缀，就是从某个位置开始到字符串结尾的特殊子串，... 查看详情

后缀数组入门——height数组与lcp(代码片段)

前言看这篇博客前，先去了解一下后缀数组的基本操作吧：后缀数组入门（一）——后缀排序。这篇博客的内容，主要建立于后缀排序的基础之上，进一步研究一个(Height)数组以及如何求(LCP)。什么是(LCP)(LCP)，即(LongestCommonPrefix)... 查看详情

后缀数组

　　今天学习了一下后缀数组，感觉是一个较为复杂且精细的数据结构，要理解它最好只抓一些关键的部分。　　首先后缀数组是建立在一个字符串上的数据结构，其存储的元素是字符串的所有后缀，譬如‘abc‘的后缀有‘c‘,... 查看详情

数据结构4——后缀数组

一、相关介绍后缀数组处理字符串的有力工具可以处理后缀自动机解决不了的问题后缀数组被称为SA，后缀自动机被称为SAM。更详细的讲解点击查看详情

后缀数组

什么是后缀数组后缀数组是处理字符串的有力工具—罗穗骞个人理解：后缀数组是让人蒙逼的有力工具！就像上面那位大神所说的，后缀数组可以解决很多关于字符串的问题，譬如这道题注意：后缀数组并不是一种算法... 查看详情

后缀数组

先说后缀是啥：后缀就是一个串s从第s[i]一直到串尾就是这个串的一个后缀，记作suffix[i]举个栗子：aacbds的后缀分别为aacbds,acbds,cbds,ds,ds,s（这是回音你懂吗是回音你懂吗回音你懂吗音你懂吗你懂吗懂吗吗）后缀数组实质就是给每... 查看详情

后缀数组（学习心得）(代码片段)

后缀数组后缀数组是一种处理字符串的利器，很多字符串的问题都可以通过后缀数组来实现。后缀数组说简单一点就是对一个字符串的所有后缀子串进行排序。我来举个例子，比如字符串banana刚开始的时候它的后缀子串... 查看详情

后缀数组（学习心得）(代码片段)

整理如何选取后缀数组&&后缀自动机

后缀家族已知成员后缀树后缀数组后缀自动机后缀仙人掌后缀预言后缀Splay？后缀树是后缀数组和后缀自动查看详情

数据结构后缀数组(代码片段)

后缀数组SuffixArray　　对于一个长度为len字符串S，将其len个后缀根据字典序排序得到的排名数组即为后缀数组　　suff[i]：表示S中起始位置为i的后缀子串（第i长的后缀）　　在求解的过程中还会维护三个数组sa/rk/height　　sa[i]：... 查看详情

使用后缀自动机求后缀数组

倒序建立后缀自动机的fail树就是后缀树，dfs后缀树得到后缀数组#include<bits/stdc++.h>usingnamespacestd;intlast,dis[200001],val[200001],cnt,a[200001][26],fa[200001],sa[200001],n,sta[200001],top;inttr[200001][26],rank[200001] 查看详情

poj2774后缀自动机&后缀数组

...，求最长公共子串。好像可以哈希切掉，但是为了练一练后缀数组以及学一学后缀自动机，我用不同方法终于A掉了这道题。后缀数组：就是求出height数组然后扫一遍，求出满足条件的最大值（满足条件是指height所指的两个后缀... 查看详情

后缀数组-codevs1500

后缀数组的原理很简单，将一个字符串S的所有后缀组成一个字符串数组，并排序，则以后每次判断某个字符串D是不是S的子串只需要strlen(D)*log(strlen(s))的时间复杂度。Codevs1500这题就是一道裸题，考后缀数组的生成... 查看详情

字符串匹配----后缀数组算法(代码片段)

一、什么是后缀数组：　　字符串后缀Suffix指的是从字符串的某个位置开始到其末尾的字符串子串。后缀数组SuffixArray(sa)指的是将某个字符串的所有后缀按字典序排序之后得到的数组，不过数组中不直接保存所有的后缀子串，只... 查看详情

数据结构之后缀数组

1.概述后缀数组是一种解决字符串问题的有力工具。相比于后缀树，它更易于实现且占用内存更少。在实际应用中，后缀数组经常用于解决字符串有关的复杂问题。本文大部分内容摘自参考资料[1][2]。2.后缀数组2.1 ... 查看详情

学习笔记：后缀数组

后缀数组是指对于后缀排序后，每个后缀的位置：sa[rank]=pos:排名为rank的后缀是pos->len这个后缀note:rank[pos]=rank:位置为pos的串排名为rank白书上的代码简洁明了，很容易理解。核心思想：我们对于每个位置开始的后缀，不直接计... 查看详情