Abstract
中文摘要 讓L = {T1, T2, ..., Tl} 為一字串的集合, 其總長度為n, 以及P = P0P2...Pm−1為一長 度為m的樣本,且L 和P都建立在一固定的字母表A上。Approximate library man- agement problem 是在容許某種程度的錯誤下, 找出P發生在L中的位置。本論文提 出此以前無人關注的動態問題, 即一字串可以被加入L中或從L中刪除, 並提供其解決 方法。之前跟本論文最相近的結果為Chan et al. [3] 所提出的索引套用Trinh et al. [11]所提出的演算法, 此解法是基於compressed suffix array 以至於較複雜而難以實 作, 其搜尋時間為O(m|A| log3 n + occ log3 n)。本論文所使用的索引是建立在一新的 技巧suffix sampling 上, 簡單且容易實作, 其搜尋時間為O(m|A| log3 n+occ log2 n) 使用O(n log |A|)bits 的空間, 其中occ 為此樣本出現的次數。此索引支援字串的加入 與刪除, 其更新時間為O(|T| log |A| log n + log2 n)。