A Language Approach to String Searching Evaluation

摘要: We propose a general framework to derive average performance of string searching algorithms that preprocess the pattern. It relies mainly on languages and combinatorics words, joined some probabilistic tools. The approach is quite powerful: although we concentrate here Morris-Pratt Boyer-Moore-Horspool, it applies large class algorithms. A fairly character distribution assumed, namely Markovian one, suitable for applications such as natural or biological databases searching. time, expressed number text-pattern comparisons, proven be asymptotically Kn linearity constant given.