AN IMPROVED ADAPTIVE STRING SEARCHING ALGORITHM

Sunday's OM algorithm can reduce the number of character comparisons b y making use of information of character distribution in an alphabet. Smith's adaptive algorithm uses dynamic statistics to reduce compariso ns, and its performance is close to that of the OM algorithm in the nu mber of character comparisons. Smith's algorithm has the advantage of language independence. Its drawback is that it runs slowly because of maintaining an ordering list. This paper presents an improved adaptive method which dispenses with the ordering list. This method treats the pattern as a circle, and first compares the mismatched character in t he last checking operation. This method is slightly worse than Smith's method in the number of character comparisons, but it is much better in the running time. (C) 1998 John Wiley & Sons Ltd.