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