Constant-space string-matching in sublinear average time

✍ Scribed by Maxime Crochemore; Leszek Ga̧sieniec; Wojciech Rytter

• Book ID: 104326610
• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 462 KB
• Volume: 218
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(98)00259-x

✦ Synopsis

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 twodimensional 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).