Time-Space-Optimal String Matching

In this paper we describe a new linear-time string-matching algorithm requiring neither dynamic storage allocation nor other high-level capabilities. The algorithm can be implemented to run in linear time even on a six-head two-way finite automaton. Moreover, the automaton requires only “{= , ≠}- branching” [1]. (Decisions depend on which of the six scanned pattern or text symbols and positions are the same, but not on the particular symbols or how many symbols there are. Hence the same algorithm works even for an infinite alphabet.) A “real-time” implementation is possible on such a multihead finite automaton with a few more heads.

Authors

• Zvi Galil
• Joel I. Seiferas

Keywords

No keywords are indexed for this paper.