Constant-space string-matching in sublinear average time

Given two strings: pattern P of length m and text T of length n. The string-matching problem is to find all occurrences of the pattern P in the text T. We present a string-matching algorithms which works in o(n) average time and constant additional space for one-dimensional texts and two-dimensional arrays. This is a first attempt to the small-space string-matching problem in which sublinear time algorithms are achieved. We show that all occurrences of one- or two-dimensional patterns can be found in O( n r ) average time with constant memory, where r is the repetition size of P (size of the longest repeated subword of P).

Authors

• Maxime Crochemore
• Leszek Ga̧sieniec
• Wojciech Rytter

Keywords

No keywords are indexed for this paper.