Name
Abstract | ||
|---|---|---|
Two equal length strings s and s', over alphabets Sigma(s) and Sigmas(',) parameterize match if there exists a bijection pi : Sigma(s) --> Sigma(s'), such that pi(s) = s', where pi(s) is the renaming of each character of s via pi. Approximate parameterized matching is the problem of finding for a pattern p, at each location of a text string t, a bijection pi that maximizes the number of characters that are mapped from p to the appropriate \p\-length substring of t. Our main result is an O(nk(1.5)+mk log m) time algorithm for this problem where m = \p\ and n = \t\. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/978-3-540-30140-0_38 | ALGORITHMS ESA 2004, PROCEEDINGS |
Field | DocType | Volume |
Discrete mathematics,Substring,Combinatorics,Parameterized complexity,Bijection,Algorithmics,Existential quantification,String (computer science),Mathematics | Conference | 3221 |
ISSN | Citations | PageRank |
0302-9743 | 7 | 0.52 |
References | Authors | |
22 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Carmit Hazay | 1 | 586 | 35.54 |
| Moshe Lewenstein | 2 | 1214 | 76.97 |
| Dina Sokol | 3 | 144 | 12.84 |