Abstract
字串搜尋問題是一個已經被廣泛討論的問題, 有許多的方法被提出來過. 如果給定一文章 T及另一較短的字串 P,我們要在 T中找到 P的所有存在 位置, 已存在好幾個方法可在 O ( m + n )的最佳時間內完成. 字串搜尋 還有一些類似的變形, 譬如具有萬用字元的字串搜尋問題, 如果給定的 P 中可以含有一個或多個萬用字元, 舉個例子來說,給定 p=ab*bc,T= bababcaaa,其中* 為萬用字元, 它可取代任意個字元或空字串, 則這例子 在 T中可找到ababc 這一字串符合 P .這樣一個問題, 在已發表的文章 中, 要將所有的答案找出來仍需 O ( m n )的時間, 其中 m為 P的長 度, n為 T的長度.上面提到的都是對一篇文章只做一次搜尋, 如果我們 考慮在一篇很長的文章 T上,會有許多次的搜尋在上面, 則我們會考慮 對 T做一些預先處理, 以期望能縮短每次的搜尋時間. Suffix tree 是我 們所熟知的一個資料結構, 它根據 T的所有 suffixes 建成一棵搜尋樹, 這棵樹可以在 O ( n ) 的時間內建成, 建成後每次搜尋只需花 O ( m )的時間, 就可以找到答案.在這篇文章中我們所要研究的問題是, 有預先 處理的具有萬用字元的字串搜尋問題, 我們將提出一個方法對 T做預先處 理, 並且在預先處理之後, 每一次的搜尋都能快速的完成. 在我們的方法 中, 對 T做完預先處理後, 我們每次搜尋只需花 O ( m )的時間, 就能完 成搜尋, 這跟一般字串搜尋建 suffix tree後的搜尋時間是相同的. 在預 先處理的部份, 則需要花 O ( n ^ 2 )的時間與空間.