zbMATH — the first resource for mathematics

Fast parallel and serial approximate string matching. (English) Zbl 0685.68033
Summary: Consider the string matching problem, where differences between characters of the pattern and characters of the text are allowed. Each difference is due to either a mismatch between a character of the text and a character o the pattern, or a superfluous character in the text, or a superfluous character in the pattern. Given a text of length n, a pattern of length m and an integer k, we present parallel and serial algorithms for finding all occurrences of the pattern in the text with at most k differences. The parallel algorithm requires O(log m\(+k)\) time using n processors. The series algorithm runs in O(nk) time for an alphabet whose size is fixed.

68W99 Algorithms in computer science
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX Cite
Full Text: DOI