1.后缀：后缀指的是从字符串的某个位置i到字符串末尾的子串，我们定义以s的第i个字符为第一个元素的后缀为suff(i)。
2.后缀数组sa[i]表示排名为i的后缀的起始位置的下标。
3.ran(i)表示起始位置的下标为i的后缀排名。
4.LCP(i,j)表示suff(sa[i])与suff(sa[j])的最长公共前缀。 则有下面的公式：
LCP(i,j)=LCP(j,i)
LCP(i,i)=len(sa[i])=n-sa[i]+1;
5.Hight[i]表示后缀子串排好序之后，排序为i与i-1的最长公共前缀是多少LCP(i,i-1)。具体的Hight[i]如下图：
后缀数组算法介绍
2024-07-11
41
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《
阿里云开发者社区用户服务协议》和
《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写
侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：
后缀数组学习
相关文章
|
6月前
|
算法
|
6月前
|
算法
NoSQL
容器
|
6月前
|
算法
|
算法
|
算法
|
算法
|
存储
算法
BI
|
算法
|
机器学习/深度学习
存储
容器
|
算法
热门文章
最新文章
1
3分钟部署 我的世界（Minecraft） 联机服务
2
快速部署 RAGFlow 社区版
3
Spring Boot 3 + JWT + Security 联手打造安全帝国：一篇文章让你掌握未来！
4
解决http下navigator.clipboard为undefined问题
5
3分钟部署 灵魂面甲（SOULMASK）联机服务
6
产品动态丨阿里云计算巢月刊-2024年第10期
7
Docker Hub 镜像拉取超时：1Panel面板中应用安装失败的临时解决方案
8
解决SpringBoot中@RequestBody不能和Multipart同时传递的问题
9
使用Ollama和Open WebUI管理本地开源大模型
10
Java“Broken Pipe”解决