Name
Abstract | ||
|---|---|---|
We say that two sequences x and w of length m are order-isomorphic (of the same “shape”) if w[i]⩽w[j] if and only if x[i]⩽x[j] for each i,j∈[1,m]. We present a simple linear time algorithm for checking if a given sequence y of length n contains a factor which is order-isomorphic to a given pattern x. A factor is a subsequence of consecutive symbols of y, so we call our problem the consecutive permutation pattern matching. The (general) permutation pattern matching problem is related to general subsequences and is known to be NP-complete. We show that the situation for consecutive subsequences is significantly different and present an O(n+m) time algorithm under a natural assumption that the symbols of x can be sorted in O(m) time, otherwise the time is O(n+mlogm). In our algorithm we use a modification of the classical Knuth–Morris–Pratt string matching algorithm. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.ipl.2013.03.015 | Information Processing Letters |
Keywords | Field | DocType |
Permutation pattern matching,Pattern matching,Knuth–Morris–Pratt algorithm,Analysis of algorithms | Discrete mathematics,Knuth–Morris–Pratt algorithm,Combinatorics,Analysis of algorithms,Algorithm,If and only if,Permutation pattern,Subsequence,Time complexity,Pattern matching,Mathematics | Journal |
Volume | Issue | ISSN |
113 | 12 | 0020-0190 |
Citations | PageRank | References |
30 | 1.44 | 10 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marcin Kubica | 1 | 629 | 29.26 |
| Tomasz Kulczynski | 2 | 30 | 1.78 |
| Jakub Radoszewski | 3 | 624 | 50.36 |
| Wojciech Rytter | 4 | 2290 | 181.52 |
| Tomasz Waleń | 5 | 706 | 39.62 |