Some Results on Exact String Matching Algorithm

[[abstract]]這?有二個字串問題。 一個是精確字串比對問題 (Exact String Matching Problem), 另一個則是找字串週期問題 (Period of String)。 精確字串比對問題是給定二個字串T跟P，T 字串長度為n, T字串長度為n。n大於等於m。 精確字串比對問題上我們介紹二個演算法。第一個?算法是首先從P字串來找出一個位置，此位置使得P在T上比對時給予多個移動值。我們的演算法介紹如何從P求出這個位置。 第二個演算法是先在T上開n/m 個重疊比對範圍，長度為2m-1。此比對範圍名為寬闊比對範圍。在每一個寬闊比對範圍，從中間往右方向尋找是否有P字尾出現。如果P字尾出，尋求找所對應的P字首。P字尾或P字首是否出現我們使用改良迴旋方法。 字串週期問題是給定一個字串T。T字串長度為n。 把T字串的週期利用bit parallel 方法找出來。所以在這個論文中，我們會介紹一個演算法如何在線形時間內找出字串的週期。[[abstract]]In this paper, we introduce two algorithms for stringology. One is to solve the exact string matching problem and the other is to find the string cycle (period of a string). In the exact string matching problem, we are given two strings T=t1t2...tn and P=p1p2...pm. We are asked to find all occurrences of P in T. Our searching method is based upon a single character rule. Consider a location i in P. Suppose that pi is aligned with tj and pi tj. We then must move P in such a way that some pk=tj will be aligned with tj. In the thesis, we propose a method to find the optimal location i. We also modified a string matching approach, named wide window approach, which divides the text into n/m overlapping windows of size 2m-1. In the windows, the approach attempts m possible occurrence positions in parallel. It firstly searches pattern suffixes from middle to right with the modified convolution method, shifts the window directly when it fails, otherwise, scans the corresponding prefixes backward with the modified convolution method again. For the period of string problem, we are given a string T and we are asked to find the periods of T. Our algorithm is based upon the bit parallel approach.[[note]]碩