DC3 h[i]>=h[i-1]-1证明

李恒道

由于个人功底问题

不保证正确

已知存在h[i]>=h[i-1]-1

假设当前位置为i，字符串为X

则i-1位置的字符为aX，其中a表示任意单个字符

当i-1计算最长前缀时，会找到后缀排名中的上一个，我们假设为k，k的字符是aY

则假设aX跟aY的前缀长度为3

当i-1到i，此时去掉a变成了X

而k的aY，假设去掉一位是Y

由于aY>aX，则可推断Y一定大于X

但无法否定Y一定是X的前一位排名

我们假设Y不是X的排名

要想处于Y跟X之间则一定要前2位相等才可以，是2是因为之前aY是3，我们现在删了一个a

由此可以证明X的前一排名一定存在长度为2

即证明了单调性，可得h[i]>=h[i-1]-1

参考资料
https://www.cnblogs.com/yongren1zu/p/3239270.html