Name
Abstract | ||
|---|---|---|
We consider the combination of function and permuted matching, each of which has fast solutions in their own right. Given a pattern p of length m and a text t of length n, a function match at position i of the text is a mapping f from @S"p to @S"t with the property that f(p"j)=t"i"+"j"-"1 for all j. We show that the problem of determining for each substring of the text, if any permutation of the pattern has a function match is in general NP-Complete. However where the mapping is also injective, so-called parameterised matching, the problem can be solved efficiently in O(nlog|@S"p|) time. We then give a 1/2-approximation for a Hamming distance based optimisation variant by reduction to multiple knapsack with colour constraints. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.ipl.2010.08.017 | Inf. Process. Lett. |
Keywords | Field | DocType |
general np-complete,hamming distance,permuted matching,fast solution,colour constraint,so-called parameterised matching,length n,function match,permuted function matching,pattern p,length m,approximation algorithms,theory of computation | Discrete mathematics,Combinatorics,Substring,Injective function,Permutation,Hamming distance,Knapsack problem,Function composition,Pattern matching,Mathematics,Theory of computation | Journal |
Volume | Issue | ISSN |
110 | 22 | 0020-0190 |
Citations | PageRank | References |
1 | 0.36 | 12 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Raphaël Clifford | 1 | 268 | 28.57 |
| Benjamin Sach | 2 | 93 | 11.40 |