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((n+m) log k+α) space O(m+A), where A sum lower bounds α 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, α. Our surprisingly simple straightforward implement.