A Boyer-Moore Type String Matching Algorithm with Memory and Its Computational Complexity
Xiaohua Liu · Journal of Hunan University · 2008
A new string matching automata was constructed.The automata had the advantage that each of the matching windows always kept the uniform form in which the left part in this window was a prefix of the pattern and the characters of the right part were not compared.It has been proved that each of the characters in the text is compared once at most and thus the total compared number in the matching process is less than or equal to the length n of the text.It is minimum in the upper bounds of the total compared numbers of the string matching algorithms in the worst case.When the pattern P is not quasi-cyclic,it has been proved that this algorithm is sublinear.Experiments have shown that the running speed of the algorithm is faster than the Boyer-Moore algorithm.