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
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《
阿里云开发者社区用户服务协议》和
《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写
侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：
后缀数组学习
相关文章
|
7月前
|
算法
|
7月前
|
算法
NoSQL
容器
|
7月前
|
算法
|
算法
|
算法
|
存储
算法
BI
|
算法
|
机器学习/深度学习
存储
容器
|
算法
|
算法
网络协议
 字符串算法(三) - 字符串分割](https://ucc.alicdn.com/pic/developer-ecology/e416d859678f4f3da7d9b07896ba19c2.png?x-oss-process=image/resize,h_160,m_lfit)
热门文章
最新文章
1
3分钟部署 我的世界（Minecraft） 联机服务
2
3分钟部署 灵魂面甲（SOULMASK）联机服务
3
快速部署 RAGFlow 社区版
4
Spring Boot 3 + JWT + Security 联手打造安全帝国：一篇文章让你掌握未来！
5
幻兽帕鲁服务器存档拷贝教程
6
Docker Hub 镜像拉取超时：1Panel面板中应用安装失败的临时解决方案
7
幻兽帕鲁服务器参数配置指南&参数解读&参数推荐
8
产品动态丨阿里云计算巢月刊-2024年第11期
9
解决http下navigator.clipboard为undefined问题
10
使用Ollama和Open WebUI管理本地开源大模型