String Matching in Real Time

DOI10.1145/322234.322244MaRDI QIDQ3902462zbMATH OpenOpenAlexFDO

Authors Zvi Galil

Publication date 1981

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/322234.322244

zbMATH Keywords

on-line algorithmpredictability conditionrandom access machinesTuring machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99) Algorithms in computer science (68W99)

Cited in

(12)

• String-matching on ordered alphabets
• Palindrome recognition in real time by a multitape Turing machine
• The derivation of on-line algorithms, with an application to finding palindromes
• Simple and efficient LZW-compressed multiple pattern matching
• Real-time streaming string-matching
• Simple real-time constant-space string matching
• Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model
• Simple real-time constant-space string matching
• Persistence, randomization and parallelization: On some combinatorial games and their applications (abstract)
• Pattern matching in pseudo real-time
• Window-accumulated subsequence matching problem is linear
• String matching algorithms and automata

This page was built for publication: String Matching in Real Time

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