String-matching on ordered alphabets

We present a new string-matching algorithm that exploits an ordering of the alphabet. The algorithm is linear in time and uses a fixed number of memory locations in addition to the text and the pattern. Therefore, it is time-space optimal. Its main characteristic is that it scans the pattern from left to right. No preprocessing of the pattern is needed and the complexity is independent of the size of the pattern. An important consequence is the possibility of computing the periods of a word in linear time and constant space. The algorithm can also be turned into a real-time string-matching algorithm.

Authors

• Maxime Crochemore

Keywords

No keywords are indexed for this paper.