Permutationsmusterabgleich in Zeichenfolgen

Der Permutationsmusterabgleich befasst sich grob gesagt mit Problemen der folgenden Art:

Gegebenen Permutationen in S n und σ in S m , wobei m ≤ n , tut π eine enthalten Subsequenz τ der Länge m , deren Elemente geordnet nach σ ?$\pi$$S_n$$\sigma$$S_m$$m\leq n$$\pi$ $\tau$$m$$\sigma$

Wenn beispielsweise und σ = ⟨ 2 1 3 ⟩ , dann sind die Subsequenz 3 1 4 Matches & sgr; . Wie Sie sehen können, suchen wir hier nicht nach einer genauen Übereinstimmung, sondern nach etwas, das dem angegebenen Muster "ähnelt".$\pi=\langle 3\ 1\ 5\ 4\ 2\ 8\ 6\ 7\rangle$$\sigma=\langle 2\ 1\ 3\rangle$$3\ 1\ 4$$\sigma$

Weiß jemand, ob daran gearbeitet wurde, Permutationsmuster-Matching-Probleme auf Strings auszudehnen? Google hat leider nicht geholfen, da das bekannte Pattern-Matching-Problem bei Strings nichts damit zu tun hat.

Ich habe es endlich geschafft, eine schöne Umfrage von Kitaev und Mansour zu erstellen , die Hinweise auf die Literatur zum Permutationsmusterabgleich für "übliche" / signierte / farbige Permutationen und Wörter gibt.

Baars, Löh und Swierstra implementierten Permutationsparser für Haskell (Journal of Functional Programming / Band 14 / Ausgabe 06, S. 635 - 646). Diese können verwendet werden, um die Permutation einer Sammlung von Parsern anzugeben. Wenn jeder dieser Parser ein optionaler Parser für ein einzelnes Zeichen ist (dh mit dem Zeichen oder nichts übereinstimmt), haben Sie die Zutaten, nach denen Sie suchen. Ich glaube, dass ihre Bibliothek mit GHC verfügbar ist.

Sie sollten von Revital Eres, Gad M. Landau und Laxmi Parida ausgehen: Entdeckung von Permutationsmustern in Biosequenzen . Journal of Computational Biology 11 (6): 1050 & ndash; 1060 (2004).