關于后綴數(shù)組的文件
本文介紹后綴數(shù)組的基本概念、方法以及應用。
首先介紹O(nlogn)復雜度構造后綴數(shù)組的倍增算法，接著介紹了配合后綴
數(shù)組的最長公共前綴 LCP（Longest Common Prefix）的計算方法，并給出一個
線性時間內(nèi)計算height 數(shù)組（記錄跨度為1 的LCP 值的數(shù)組）的算法。為了讓
讀者對如何運用后綴數(shù)組有一個感性認識，還介紹了兩個應用后綴數(shù)組的例子：
多模式串的模式匹配（給出每次匹配O(m+logn)時間復雜度的算法）以及求最
長回文子串（給出O(nlogn)時間復雜度的算法）。最后對后綴數(shù)組和后綴樹作了
一番比較。
標簽：
nlogn
后綴數(shù)組
基本概念
復雜度
上傳時間：
2013-12-21
上傳用戶：zhangliming420
