TY - JOUR

T1 - Constant-space string-matching in sublinear average time

AU - Crochemore, Maxime

AU - Ga̧sieniec, Leszek

AU - Rytter, Wojciech

N1 - Funding Information:
*Corresponding author. E-mail: leszek@csc.liv.ac.uk. Research supported Nuffield Foundation Awards to Newly Appointed Lecturers) award.

PY - 1999/4/28

Y1 - 1999/4/28

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

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

UR - http://www.scopus.com/inward/record.url?scp=0347653261&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0347653261&partnerID=8YFLogxK

U2 - 10.1016/S0304-3975(98)00259-X

DO - 10.1016/S0304-3975(98)00259-X

M3 - Article

AN - SCOPUS:0347653261

SN - 0304-3975

VL - 218

SP - 197

EP - 203

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1

T2 - Proceedings of the 1997 International Conference on Compression and Complexity of Sequences

Y2 - 11 June 1997 through 13 June 1997

ER -