On the Worst-Case Behavior of String-Searching Algorithms

DOI10.1137/0206048MaRDI QIDQ4142690zbMATH OpenOpenAlexFDO

Authors Ronald L. Rivest

Publication date 1977

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/762a11b27c5a3dd74cddc626da01d4e2189d6f3c

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Cited in

(9)

• String overlaps, pattern matching, and nontransitive games
• Worst-case behavior of string-searching algorithms
• Average running time of the Boyer-Moore-Horspool algorithm
• On Boyer-Moore automata
• Optimal partial-match retrieval
• On the decision tree complexity of string matching
• String Matching: Communication, Circuits, and Learning.
• Tight comparison bounds for the string prefix-matching problem
• An analysis of the Karp-Rabin string matching algorithm

This page was built for publication: On the Worst-Case Behavior of String-Searching Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4142690)