On Simon's string searching algorithm
We give sharp bounds for the problem of string matching when only one head moving from the right to the left of the text is used: \((2-1/m)n\) character comparisons for all the text, and \(\min \{1+ \log_ 2m,\text{Card}(A)\}\) character comparisons on each character of the text, where \(m\) is the length of the pattern, \(n\) the length of the text, and \(A\) the alphabet. These bounds improve on the previous bounds given by \textit{D. E. Knuth}, \textit{J. H. Morris} and \textit{V. R. Pratt} [SIAM J. Computing 6, 323-350 (1977; Zbl 0372.68005)], and, more recently, by \textit{H.-J. Simon}.
- Fast Pattern Matching in Strings
- scientific article; zbMATH DE number 3811868 (Why is no real title available?)
- scientific article; zbMATH DE number 1256698 (Why is no real title available?)
- scientific article; zbMATH DE number 1142311 (Why is no real title available?)
- scientific article; zbMATH DE number 3449757 (Why is no real title available?)
- On the Exact Complexity of String Matching: Lower Bounds
- On the Exact Complexity of String Matching: Upper Bounds
- Waiting time and complexity for matching patterns with automata
- Exact bounds on the complexity of sequential string matching algorithms
- An efficient null-free procedure for deciding regular language membership
- Validating the Knuth-Morris-Pratt failure function, fast and online
- Minimisation of automata
- On-line string matching algorithms: survey and experimental results
- On the Exact Complexity of String Matching: Upper Bounds
- A New String Matching Algorithm
- On Simon's congruence closure of a string
- String matching algorithms and automata
- Simon's congruence pattern matching
- How the character comparison order shapes the shift function of on-line pattern matching algorithms
This page was built for publication: On Simon's string searching algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685473)
