Saving Space in Fast String-Matching

DOI10.1137/0209032MaRDI QIDQ3891771zbMATH OpenOpenAlexFDO

Authors Joel I. Seiferas, Zvi Galil

Publication date 1980

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

Full work available at URL https://doi.org/10.1137/0209032

zbMATH Keywords

Turing machinefailure functionstring-matchingtime-space trade-offpattern-matchingstring periodicitymultihead finite automatoncounter simulationtext-searching

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Pattern recognition, speech recognition (68T10) Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Cited in

(11)

• Periods in strings
• Correctness and efficiency of pattern matching algorithms
• Linear-time string-matching using only a fixed number of local storage locations
• Saving comparisons in the Crochemore-Perrin string-matching algorithm
• Detecting morphic images of a word: On the rank of a pattern
• Simple real-time constant-space string matching
• Simple real-time constant-space string matching
• Time-space-optimal string matching
• Squares, cubes, and time-space efficient string searching
• Detecting the morphic images of a word : improving the general algorithm
• Efficient parameterized pattern matching in sublinear space

This page was built for publication: Saving Space in Fast String-Matching

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