Name
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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.jda.2006.03.014 | J. Discrete Algorithms |
Keywords | Field | DocType |
special case,parameterized matching,pattern matching with mismatches,algorithms,corresponding encodings,string matching,pattern matching,pattern p,approximate parameterized string,time o,respective alphabet | String searching algorithm,Discrete mathematics,Inverse,Combinatorics,Parameterized complexity,Ackermann function,Function composition,Pattern matching,Mathematics,Binary number,Special case | Journal |
Volume | Issue | ISSN |
5 | 1 | Journal of Discrete Algorithms |
Citations | PageRank | References |
22 | 0.81 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alberto Apostolico | 1 | 1441 | 182.20 |
| Péter L. Erds | 2 | 23 | 2.21 |
| Moshe Lewenstein | 3 | 1214 | 76.97 |