×

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.

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