Tag Archives: 后缀数组

后缀数组 – 扫盲篇

一、后缀的定义

后缀数组,做为后缀树的替代品,可以解决很多棘手的字符串处理问题。

长度为n的String[0, 1…n-1]

定义后缀Suffix(i)=sub_string[i…n-1]。

例如字符串aabaaaab,Suffix[1] = abaaaab,Suffix[7]=b。

考虑到空间问题,以及C系列语言中,Suffix[i]非常好求得(&str[i]即可)。一般不会保存Suffix[i]这个数组。

二、后缀数组sa和逆运算数组ran[……]

继续阅读