A linear time algorithm for consecutive permutation pattern matching

• We give a simple linear time algorithm for permutation consecutive pattern matching.
• Our algorithm is based on the Knuth–Morris–Pratt algorithm.
• This is the first algorithmic study of consecutive permutation patterns.

We say that two sequences x and w of length m   are order-isomorphic (of the same “shape”) if w[i]⩽w[j]w[i]⩽w[j] if and only if x[i]⩽x[j]x[i]⩽x[j] for each i,j∈[1,m]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)O(n+m) time algorithm under a natural assumption that the symbols of x   can be sorted in O(m)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.