String Matching in Real Time

DOI10.1145/322234.322244zbMath0454.68009OpenAlexW1967384930MaRDI QIDQ3902462

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

Turing machineson-line algorithmrandom access machinespredictability condition

Mathematics Subject Classification ID

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

Related Items (13)

Persistence, randomization and parallelization: On some combinatorial games and their applications (abstract) ⋮ Full-fledged real-time indexing for constant size alphabets ⋮ Simple real-time constant-space string matching ⋮ String matching algorithms and automata ⋮ Simple and efficient LZW-compressed multiple pattern matching ⋮ String-matching on ordered alphabets ⋮ 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 ⋮ Pattern matching in pseudo real-time ⋮ Window-accumulated subsequence matching problem is linear ⋮ Palindrome recognition in real time by a multitape Turing machine ⋮ The derivation of on-line algorithms, with an application to finding palindromes

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