# Permutation pattern matching in strings

Loosely speaking, permutation pattern matching deals with problems of the following kind:

Given permutations $\pi$ in $S_n$ and $\sigma$ in $S_m$, with $m\leq n$, does $\pi$ contain a subsequence $\tau$ of length $m$ whose elements are ordered according to $\sigma$?

For example, if $\pi=\langle 3\ 1\ 5\ 4\ 2\ 8\ 6\ 7\rangle$ and $\sigma=\langle 2\ 1\ 3\rangle$, then the subsequence $3\ 1\ 4$ matches $\sigma$. As you can see, we're not looking here for an exact match, but rather for something that "looks like" the specified pattern.

Does anyone know whether work has been conducted on extending permutation pattern matching problems to strings? Google unfortunately did not help, since the well-known pattern matching problem on strings has nothing to do with this.

• I'm currently doing research in affine permutation patterns. There is some work out there but most of it is only available to those in academia. – abigail3306 Feb 12 '14 at 5:29