Pencocokan pola permutasi dalam string

Secara longgar, pola permutasi cocok dengan masalah-masalah seperti ini:

Mengingat permutasi di dan di , dengan , tidak mengandung subsequence panjang yang unsur-unsurnya dipesan sesuai ?$\pi$$S_n$$\sigma$$S_m$$m\leq n$$\pi$ $\tau$$m$$\sigma$

Misalnya, jika dan , maka urutan cocok . Seperti yang Anda lihat, kami tidak mencari pasangan yang tepat di sini, tetapi mencari sesuatu yang "mirip" dengan pola yang ditentukan.$\pi=\langle 3\ 1\ 5\ 4\ 2\ 8\ 6\ 7\rangle$$\sigma=\langle 2\ 1\ 3\rangle$$3\ 1\ 4$$\sigma$

Apakah ada yang tahu apakah pekerjaan telah dilakukan untuk memperluas masalah pencocokan pola permutasi ke string? Google sayangnya tidak membantu, karena masalah pencocokan pola yang terkenal pada string tidak ada hubungannya dengan ini.

Saya akhirnya berhasil menggali survei yang bagus dari Kitaev dan Mansour , yang memberi petunjuk pada literatur yang berkaitan dengan pola permutasi yang cocok dengan permutasi dan kata-kata "biasa" / bertanda / berwarna.

Baars, Löh, dan Swierstra mengimplementasikan Permutasi Parsers untuk Haskell (Jurnal Pemrograman Fungsional / Volume 14 / Edisi 06, hal 635 - 646). Ini dapat digunakan untuk menentukan permutasi koleksi parser. Jika masing-masing parser ini adalah parser opsional untuk satu karakter (yaitu, cocok dengan karakter atau tidak sama sekali), maka Anda akan memiliki bahan yang Anda cari. Saya percaya bahwa perpustakaan mereka tersedia dengan GHC.

Anda harus mulai dari Revital Eres, Gad M. Landau, Laxmi Parida: Penemuan Pola Permutasi dalam Biosequences . Jurnal Komputasi Biologi 11 (6): 1050-1060 (2004).