A Technique for Extending Rapid Exact-Match String Matching to Arrays of More than One Dimension
Author:
- Theodore P. BakerTBTheodore P. Baker
- 1 November 1978
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 7 (4) , 533-541
Abstract
A class of algorithms is presented for very rapid on-line detection of occurrences of a fixed set of pattern arrays as embedded subarrays in an input array. By reducing the array problem to a string matching problem in a natural way, it is shown that efficient string matching algorithms may be applied to arrays. This is illustrated by use of the string-matching algorithm of Knuth, Morris and Pratt [7]. Depending on the data structure used for the preprocessed pattern graph, this algorithm may be made to run “real-time” or merely in linear time. Extensions can be made to nonrectangular arrays, multiple arrays of dissimilar sizes, and arrays of more than two dimensions. Possible applications are foreseen to problems such as detection of edges in digital pictures and detection of local conditions in board games.Keywords
This publication has 8 references indexed in Scilit:
- A fast string searching algorithmCommunications of the ACM, 1977
- Saving space in fast string-matching1977
- Fast Pattern Matching in StringsSIAM Journal on Computing, 1977
- A Space-Economical Suffix Tree Construction AlgorithmJournal of the ACM, 1976
- Real-time algorithms for string-matching and palindrome recognition1976
- Linear pattern matching algorithms1973
- Rapid identification of repeated patterns in strings, trees and arrays1972
- On the computational complexity of algorithmsTransactions of the American Mathematical Society, 1965