导图社区 后缀数组
这是一篇关于后缀数组的思维导图,主要内容有详细解答、要点、两种做法、作用、主要数组。
后缀数组是处理字符串的有力工具。后缀数组是后缀树的一个非常精巧的替代品,它比后缀树容易编程实现,能够实现后缀树的很多功能而时间复杂度也并不逊色。
C++后缀数组简介,包括Icp、关键词、后缀例子、详细解答、要点、两种做法、作用、主要数组这些方面作了介绍。
社区模板帮助中心,点此进入>>
论语孔子简单思维导图
《傅雷家书》思维导图
《童年》读书笔记
《茶馆》思维导图
《朝花夕拾》篇目思维导图
《昆虫记》思维导图
《安徒生童话》思维导图
《鲁滨逊漂流记》读书笔记
《这样读书就够了》读书笔记
妈妈必读:一张0-1岁孩子认知发展的精确时间表
后缀数组
详细解答
要点
下标从1开始
两种做法
倍增
O(nlogn)
CD3
O(n)
作用
将所有后缀按字典序排序
主要数组
sa[i]
排名第i位的是第几个后缀
rk[i]
hergnt[i]
sa[i]和sa[i-1]的最长公共前缀
简要求法
hergnt[i]=lcp(i-1,j)
h(i)
第i个后缀和排名在它前面一位的后缀这两个后缀之间的最长公共前缀的长度
第i个后缀的排名是多少
h(i)=hergnt[rk[i]]
性质
h(i)≥h(i-1)-1
k=h(i-1)≥h(i-2)-1
k
变化
减n次
-n→+n
后缀例子
aababb
ababb
babb
abb
bb
b
关键字
lcp
lcp(i,j)概念
排名第i位的后缀和第j位的后缀的最长公共前缀
公式
lcp(i,j)=lcp(j,i)
和i,j顺序无关
lcp(i,i)=len(i)
第i个后缀的长度
lcp(i,j)=min(lcp(i,k),lcp(k,j))
原为≥,由夹逼定理得=
证明
引申
lcp(i,j)=min(lcp(i,i+1),lcp(i+1,i+2)……lcp(j-1,j)
证明: k+1个后缀一定排在第i个后缀的上面 且它们的最长公共前缀等于这两个公共前缀去掉第一个字母 因为他们只有第一个字母不同
夹逼定理:函数A>B,函数B>C,函数A的极限是X,函数C的极限也是X ,那么函数B的极限就一定是X,这个就是夹逼定理。
i<j,i>j即交换,i≤k≤j