DC3 h[i]>=h[i-1]-1证明
由于个人功底问题不保证正确
已知存在h>=h-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>=h-1
参考资料
https://www.cnblogs.com/yongren1zu/p/3239270.html
页:
[1]