On the exact complexity of string matching
- 4 December 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 135-144
- https://doi.org/10.1109/fscs.1990.89532
Abstract
The maximal number of character comparisons made by a linear-time string matching algorithm, given a text string of length n and a pattern string of length m over a general alphabet, is investigated. The number is denoted by c(n,m) or approximated by (1+C)n, where C is a universal constant. The subscript 'online' is added when attention is restricted to online algorithms, and the superscript '1' is added when algorithms that find only one occurrence of the pattern in the text are considered. It is well known that nKeywords
This publication has 13 references indexed in Scilit:
- The Boyer–Moore–Galil String Searching Strategies RevisitedSIAM Journal on Computing, 1986
- Finding the median requires 2n comparisonsPublished by Association for Computing Machinery (ACM) ,1985
- A Unified Lower Bound for Selection and Set Partitioning ProblemsJournal of the ACM, 1981
- A New Proof of the Linearity of the Boyer-Moore String Searching AlgorithmSIAM Journal on Computing, 1980
- On improving the worst case running time of the Boyer-Moore string matching algorithmCommunications of the ACM, 1979
- A fast string searching algorithmCommunications of the ACM, 1977
- Fast Pattern Matching in StringsSIAM Journal on Computing, 1977
- A sorting problem and its complexityCommunications of the ACM, 1972
- An axiomatic basis for computer programmingCommunications of the ACM, 1969
- A Tournament ProblemThe American Mathematical Monthly, 1959