Permutation pattern matching in strings
I finally managed to dig out a nice survey by Kitaev and Mansour, which gives pointers to the literature related to permutation pattern matching on  "usual"/signed/coloured permutations and words.