A K-modular String Matching Algorithm

[[abstract]]字串比對演算法是很廣泛的被使用在搜尋上的演算法，且已有很多人發表過多種不同做法。而這些演算法中，有的處理速度非常快速，像Boyer -Moore 演算法，可是很難分析它的時間複雜度；暴力法很直覺，做法單純，但其時間複雜度為O(m*n)(m為比對字串長，n為本文長)。而Morris-Pratt(MP)演算法與Knuth-Morris-Pratt (KMP)演算法雖然簡單且時間複雜度為O(n)，但每個字元仍需至少比對一次。Colussi演算法則是一種奇特的演算法，分成兩個階段，第一部利用Knuth-Morris-Pratt (KMP)的前置處理表格，由左至右跳過一些字元，第二階段再由右自左比對這些跳過的字元，這樣的做法速度上會比MP演算法、KMP演算法更快，不過分析的方式卻不是那麼的直覺。所以我們試圖尋找一種既簡單又容易分析的演算法。我們的演算法也跟Colussi演算法一樣分成兩個階段，第一階段由左至右每隔k個字元比對一次，第二階段再從最左邊依序比對，但跳過已比對過的字元。演算法很簡單且跟KMP演算一樣很容易分析，但比對的次數少於KMP演算。[[abstract]]Lots of string matching algorithms has been proposed. Among them, Boyer-Moore is fast but difficult to analyze its time complexity. The naive, or brute force, algorithm is the simplest string matching method. Its time complexity is O(m*n) when searching with a pattern of length m in a text of length n. Although Morris Pratt (MP) and Knuth-Morris-Pratt (KMP) algorithm method are very simple, and their time complexity is O(n), but every character must be checked at lease once. Colussi method, the one most peculiar method, divides its process into two step. The first step, is by using Knuth-Morris-Pratt (KMP) prefix function table, scans from left to right and leaps some characters. The second step searches from right to left on the characters missed by the first step. By this method, it searches faster than KMP method, but the time analysis is not so simple as KMP’s. Therefore we try to find a method which is simple and is easy to analyse. Our method also have two step similar with Colussi’s. The first step is to compare character from left to right every k characters, then the second step, also starting from the left side, is to check the un-compared characters. This method is simple and easy to analyze as KMP’s, but the number of comparisons is lower than KMP’s[[note]]碩