Fast Pattern Matching in Strings

Summary

An algorithm is presented which finds all occurrences of one given string within another, in running time proportional to the sum of the lengths of the strings, showing that the set of concatenations of even palindromes, i.e., the language α α ^R^*, can be recognized in linear time.

Keywords

String searching algorithm, Algorithm, Pattern matching, Mathematics, Matching (statistics)

References

MITのArtificial Intelligence Laboratory良明白井 — 1973
STRING-MATCHING AND OTHER PRODUCTSManuela Fischer, Mike Paterson — 1974
Linear Time Simulation of Deterministic Two-Way Pushdown AutomataStephen Cook — 1971
The Design and Analysis of Computer AlgorithmsAlfred V. Aho, John E. Hopcroft — 1974
Uniqueness theorems for periodic functionsN. J. Fine, Herbert S. Wilf — 1965
Sur une question de Jean BernoulliA. Markoff — 1881
On converting on-line algorithms into real-time and on real-time algorithms for string-matching and palindrome recognitionZvi Galil — 1975
Implementation of the substring test by hashingMalcolm C. Harrison — 1971
On the Translation of Languages from Left to RightDonald E. Knuth — 1965
A New Linear-Time ``On-Line'' Algorithm for Finding the Smallest Initial Palindrome of a StringGlenn K. Manacher — 1975
Synchronization of binary messagesE. N. Gilbert — 1960
A fast string searching algorithmRobert S. Boyer, J Strother Moore — 1977
Structured Programming with go to StatementsDonald Knuth — 1974
Elementary number theoryGareth A. Jones, J.M. Jones — 1959
Rapid identification of repeated patterns in strings, trees and arraysRichard M. Karp, Raymond E. Miller, Arnold L. Rosenberg — 1972
Linear Pattern Matching AlgorithmsPeter Weiner — 1973
The Art of Computer ProgrammingG.E. Whitesides — 1968
E2307D. M. Bloom, Donald E. Knuth — 1972
Elementary Number Theory.Merrill Barnebey, Underwood Dudley — 1970
The art of computer programming. Vol.1: Fundamental algorithmsDonald E. Knuth — 1978

Cited by

Algorithmique parallèle du texte : du modèle systolique au modèle CGMThierry Garcia — 2003
Hardware acceleration of network intrusion detection and preventionBrendan Cronin — 2014
An enhanced sub image matching algorithm for binary imagesAzzam Sleit, Heba Saadeh, Ibraheem Al-Dhamari — 2010
Partial evaluation of lazy functional logic programs: ThesisPascual Julián-Iranzo — 2003
Reconfigurable processing architectures for stream processing and hybrid computingJohn A. Chandy, Janardhan Singaraju — 2011
Parsing with Prefix and Suffix Dictionaries.Martin Cohn, Roger Khazan — 1996
SNP and mutation discovery using base-specific cleavage and MALDI-TOF mass spectrometryCarmen Galán López — 2003
Prospects and limitations of full-text index structures in genome analysisJodie Dalgleish — 2012
Suffix trees and their applications in string algorithmsRoberto Grossi, Giuseppe F. Italiano — 1993
On Succinct Representations of Textured Surfaces by Weighted Finite AutomataJürgen Albert, German Tischler — 2010
Tight bounds for data stream algorithms and communication problemsMert Sağlam — 2011
Geometric Point Pattern Matching in the Knuth-Morris-Pratt WayEsko Ukkonen — 2010
An Efficient Algorithm for Recognizing the Forward-Branching Class of Term-Rewriting SystemsAlain Miniussi, Robert Strandh — 1997
Narrowing-driven Specialization of Functional Logic ProgramsMarı́a Alpuente, Moreno Falaschi, Germán Vidal — 2004
Program and Data Specialization Principles, Applications, and Self-ApplicationKaroline Malmkjær — 1989
Border Array on Bounded AlphabetJean-Pierre Duval, Thierry Lecroq, Arnaud Lefebvre — 2002
Mitigating Botnet-based DDoS Attacks against Web ServersPeter L. Djalaliev — 2013
BioSuite: a comprehensive bioinformatics software package (A unique industry-academia collaboration)M. Vidyasagar, Shekhar C. Mande, Sachin Rajgopal — 2007
Robust String Matching in O(√N+M) Quantum QueriesChris Lomont — 2003
Automatic Malware Signature GenerationKarin Ask — 2006

Related papers

Computer Algorithms: String Pattern Matching StrategiesJun‐ichi Aoe — 1994
Two Improved Fast Single Pattern Matching Algorithms of QSZhou Zhi-pin — 2013
A single-pattern matching algorithm base on twice jumps in the intrusion detection systemsZhongming Yang, Lin Shen — 2015
A New pattern matching algorithm and parallelization design in IDSLiu Fang-ai — 2005
Largest Shift String Matching Algorithm: Blend of Berry Ravindran, Zhu-Takaoka and Back & Forth Matching AlgorithmMd. Mahbubul Hasan, Prince Mahmud, Mst. Merina Khatun — 2022
Two-way Comparative Pattern Matching Algorithm Suitable for ChineseYu Ye — 2011
Improved BM Pattern Matching AlgorithmFeng Jingjing — 2011
A Fast Exact Pattern Matching Algorithm for Biological SequencesYong Huang, Lingdi Ping, Xuezeng Pan — 2008
Average time complexity analysis of Commentz-Walter algorithmS. D. Dewasurendra, SM Vidanagamachchi — 2018
On converting on-line algorithms into real-time and on real-time algorithms for string-matching and palindrome recognitionZvi Galil — 1975