Name
Abstract | ||
|---|---|---|
Parameterized matching between two strings occurs when it is possible to reduce the first one to the second by a renaming of the alphabet symbols. We present an algorithm for searching for parameterized occurrences of a patten in a textstring when both are given in run-length encoded form. The proposed method extends to alphabets of arbitrary yet constant size with O(|r"p|x|r"t|) time bounds, previously achieved only with binary alphabets. Here r"p and r"t denote the number of runs in the corresponding encodings for p and t. For general alphabets, the time bound obtained by the present method exhibits a polynomial dependency on the alphabet size. Such a performance is better than applying convolution to the cleartext, but leaves the problem still open of designing an alphabet independent O(|r"p|x|r"t|) time algorithm for this problem. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.tcs.2012.03.018 | Theor. Comput. Sci. |
Keywords | Field | DocType |
independent o,alphabet size,time bound,binary alphabet,alphabet symbol,present method,run-length encoded string,constant size,time algorithm,general alphabet | Combinatorics,Parameterized complexity,Substring,Bijection,Existential quantification,Computer science,Bipartite graph | Journal |
Volume | ISSN | ISBN |
454, | 0302-9743 | 3-642-16320-3 |
Citations | PageRank | References |
2 | 0.37 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alberto Apostolico | 1 | 1441 | 182.20 |
| Péter L. Erdös | 2 | 267 | 46.75 |
| Alpár Jüttner | 3 | 422 | 25.50 |