2015/09/30 by Srikrishnan Divakaran, Divakaran, Srikrishnan · 1 voice
Computer Science · Biochemistry, Genetics and Molecular Biology · #Algorithms and Data Compression #DNA and Biological Computing #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1509.09228
Given a pattern string P of length n and a query string T of length m, where the characters of P and T are drawn from an alphabet of size Δ, the \em exact string matching problem consists of finding all occurrences of P in T. For this problem, we present algorithms that in O(nΔ2) time pre-process P to essentially identify sparse(P), a rarely occurring substring of P, and then use it to find occurrences of P in T efficiently. Our algorithms require a worst case search time of O(m), and expected search time of O(m/min(|sparse(P)|, Δ)), where |sparse(P)| is at least δ (i.e. the number of distinct characters in P), and for most pattern strings it is observed to be Ω(n1/2).