The problem of approximate parameterized string searching consists of finding, for a given text t=t"1t"2...t"n and pattern p=p"1p"2...p"m over respective alphabets @S"t and @S"p, the injection @p"i from @S"p to @S"t maximizing the number of matches between @p"i(p) and t"it"i"+"1...t"i"+"m"-"1(i=1,2,...,n-m+1). We examine the special case where both strings are run-length encoded, and further restrict to the case where one of the alphabets is binary. For this case, we give a construction working in time O(n+(r"pxr"t)@a(r"t)log(r"t)), where r"p and r"t denote the number of runs in the corresponding encodings for y and x, respectively, and @a is the inverse of the Ackermann's function.

Parameterized matching with mismatches.

APOSTOLICO, ALBERTO;
2007

Abstract

The problem of approximate parameterized string searching consists of finding, for a given text t=t"1t"2...t"n and pattern p=p"1p"2...p"m over respective alphabets @S"t and @S"p, the injection @p"i from @S"p to @S"t maximizing the number of matches between @p"i(p) and t"it"i"+"1...t"i"+"m"-"1(i=1,2,...,n-m+1). We examine the special case where both strings are run-length encoded, and further restrict to the case where one of the alphabets is binary. For this case, we give a construction working in time O(n+(r"pxr"t)@a(r"t)log(r"t)), where r"p and r"t denote the number of runs in the corresponding encodings for y and x, respectively, and @a is the inverse of the Ackermann's function.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/108887
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 40
  • ???jsp.display-item.citation.isi??? ND
  • OpenAlex ND
social impact