摘要： 子串: 字符串s的子串r[i..j],i<=j,表示r串中從 i 到 j 這一段。后綴: 后綴是從某個位置 i 開始到整個串末尾結束的一個特殊子串。 也就是說suffix(i)=r[i..len(s)];后綴數組：后綴數組sa是一個一維數組，它保存的是1..n的某個排列. sa[1],sa[2],..,sa[n],并保證suffix(sa[i]) < suffix(sa[i+1]) 也就是將s的n個后綴從小到在進行排序之后把排好序的后綴 的開頭位置順序放入sa中。名次數組：名次數組rank[i]保存的是suffix(i)在所有后綴中從小到大排列的名次。后綴... 閱讀全文