Equidistant Letter Sequences und Regular Expressions

Heute hat mich per WebForm Jemand gefragt ob Wörter aus äquidistante Buchstabensequenzen (ELS) mit regulären Ausdrücken erkannt werden können. Beispielsweise soll geprüft werden, ob das Wort "foo" als ELS im Text "abf1 2o 3bor z32" vorkommt (tut es, mit Intervalllänge 4 (f suchen, dann jeweils 3 Zeichen überspringen)).

Eine äquidistande Buchstabensequenz mit unbekannter und beliebig grosser Intervalllänge n ist keine reguläre Sprache und kann folglich nicht mit einem regulären Ausdruck beschrieben werden. Dies kann einfach mit dem Pumping Lemma bewiesen werden.

Falls allerdings das gesuchte Wort bekannt und die Intervalllänge mit einem Maxima m eingegrenz werden kann (n<=m) ist die Sprache regulär und kann mit einem regulären Ausdruck beschrieben werden - wenn auch mit einem hässlichen: "(f.{0}o.{0}o|f.{1}o.{1}o|f.{2}o.{2}o|...|f.{m}o.{m}o)" (Das Pattern muss m mal wiederholt werden, mit jeweils inkrementierter Zahl zwischen den geschweiften Klammern).

Falls ELS im grösseren Rahmen erkannt werden sollten, lohnt es sich wohl einen kleinen eigenen Parser zu schreiben statt die Regex zu verwenden - mit einem solchen einfachen spezialisierten Parser ergibt sich die Intervalllängenbeschränkung, und das ganze wird wahrscheinlich wesentlich performanter ablaufen...