String matching with variable length gaps

摘要: We consider string matching with variable length gaps. Given a T and pattern P consisting of strings separated by gaps (arbitrary in specified range), the problem is to find all ending positions substrings that match P. This basic primitive computational biology applications. Let m n be lengths T, respectively, let k number present new algorithm achieving time O([email protected]) space O(m+A), where A sum lower bounds @a total occurrences within T. Compared previous results this bound essentially achieves best known complexities simultaneously. Consequently, our obtains for almost combinations m, n, k, A, @a. Our surprisingly simple straightforward implement. also algorithms finding encoding every pattern.