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
38
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《
阿里云开发者社区用户服务协议》和
《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写
侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：
后缀数组学习
相关文章
|
5月前
|
人工智能
算法
测试技术
|
5月前
|
算法
|
5月前
|
算法
NoSQL
容器
|
5月前
|
算法
C#
|
5月前
|
算法
|
算法
|
存储
算法
Java
|
算法
|
存储
算法
BI
|
机器学习/深度学习
存储
容器
热门文章
最新文章
1
解决http下navigator.clipboard为undefined问题
2
快速部署 RAGFlow 社区版
3
Docker Hub 镜像拉取超时：1Panel面板中应用安装失败的临时解决方案
4
web端实现rtsp实时推流视频播放可行性方案
5
「移动端」Android平台签名证书(.keystore)生成指南
6
Java“解析时到达文件末尾”解决
7
快速部署 Dify 社区版
8
arm安装docker与docker-copose
9
Spring Boot 3 + JWT + Security 联手打造安全帝国：一篇文章让你掌握未来！
10
如何在阿里云快速启动LobeChat轻松打造私人智能聊天助手