Efficient string matching in the presence of errors
- 1 January 1985
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 126-136
- https://doi.org/10.1109/sfcs.1985.22
Abstract
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 of 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 an algorithm for finding all occurrences of the pattern in the text, each with at most k differences. The algorithm runs in O(m2 + k2n) time. Given the same input we also present an algorithm for finding all occurrences of the pattern in the text, each with at most k mismatches (superfluous characters in either the text or the pattern are not allowed). This algorithm runs in O(k(m logm + n)) time.Keywords
This publication has 11 references indexed in Scilit:
- Efficient string matching with k mismatchesTheoretical Computer Science, 1986
- Finding approximate patterns in stringsJournal of Algorithms, 1985
- An O(n log n) algorithm for finding all repetitions in a stringJournal of Algorithms, 1984
- Optimal parallel algorithms for string matchingPublished by Association for Computing Machinery (ACM) ,1984
- Time-space-optimal string matchingJournal of Computer and System Sciences, 1983
- On approximate string matchingLecture Notes in Computer Science, 1983
- The theory and computation of evolutionary distances: Pattern recognitionJournal of Algorithms, 1980
- A fast string searching algorithmCommunications of the ACM, 1977
- Fast Pattern Matching in StringsSIAM Journal on Computing, 1977
- The String-to-String Correction ProblemJournal of the ACM, 1974