A Fast Heuristic for Exact String Matching

الأصل · EN

Given a pattern string P of length n consisting of δ distinct characters and a query string T of length m, where the characters of P and T are drawn from an alphabet Σ of size Δ, the exact string matching problem consists of finding all occurrences of P in T. For this problem, we present a randomized heuristic that in O(nδ) time preprocesses P to identify sparse(P), a rarely occurring substring of P, and then use it to find all occurrences of P in T efficiently. This heuristic has an expected search time of O(m/min(|sparse(P)|, Δ)), where |sparse(P)| is at least δ. We also show that for a pattern string P whose characters are chosen uniformly at random from an alphabet of size Δ, E[|sparse(P)|] is Ω(Δlog (2Δ/2Δ-δ)).