在這篇論文中,我們對於以Burrows-Wheeler Transform (簡稱BWT) 來解決字串比對問題有相當大的興趣,使用BWT的問題在於為某個字串產生出BWT非常耗費時間,我們的方法是以KSS的方法為基礎來修改並產生出BWT。我們的方法較KSS更簡單理解並實作,而且我們的實驗結果也顯示出我們產生出BWT的方法相當有效率。同時,我們也對最大重複子字串的問題感到相當大的興趣,也依照我們產生出BWT的方法稍做修改之後並利用到解決此問題上,舉例來說,我們的實驗裡,有一串長度為155606181個字的DNA序列,在這麼長的序列中找到長度大於2000的重複子字串只花了我們226秒,我們也成功找出了55對最大重複子字串。
In this thesis, we are interested in the Burrows-Wheeler Transform (BWT for short) for exact string matching. The problem of BWT is that it is very time-consuming to construct BWT. We have developed a method which is based upon the KSS Method to construct BWT. Our method is quite easy to comprehend and implement. Experimental results show that our method is efficient. We are also interested in the maximal repeating group problem. We have developed an efficient method to find maximal repeating groups. For example, for a DNA sequence with length 155606181, it took only 226 seconds to find 55 maximal repeating groups with lengths longer than 2000.