Inverse Regex von Zinseszins

9

Koronkorko ist das finnische Wort für Zinseszins . Wir wollen kein Zinseszins für unsere Zeichenfolgen, also finden wir den kürzestmöglichen regulären Ausdruck, um ihn auszuschließen.

Bestimmen Sie bei einer Zeichenfolge, die nur aus den Großbuchstaben AZ besteht, den kürzestmöglichen regulären Ausdruck, der mit der Zeichenfolge übereinstimmt, wenn er die Teilzeichenfolge nicht enthält KORONKORKO. Zeichenfolgen, die KORONKORKOals Teilzeichenfolge enthalten sind, sollten nicht mit dem regulären Ausdruck übereinstimmen.

Nur die Zeichen A- Z, [, ], -, ^, , ?, *, +, |, (, und )sollen in dem Ausdruck verwendet werden.

Ich denke, dies kann mit 118 Zeichen im Ausdruck erfolgen. Kannst du es kürzer machen?

Hinweis: Diese Herausforderung stammt von Ohjelmointiputka (auf Finnisch).

code-golf regular-expression Gast
quelle
Wenn !ein erlaubtes Zeichen wäre, hätten Sie es ^((?!KORONKORO).)*$für 19 Bytes tun können .
Mama Fun Roll
3
@ MamaFunRoll Ich denke, deshalb ! ist das nicht erlaubt.
Alex A.
Ich hatte den Spaß, mich auf der finnischen Website zurechtzufinden, und ich glaube, Sie suchen nach theoretischen Regex-Ausdrücken, die mit der Eingabezeichenfolge übereinstimmen / diese ablehnen. Beispielsweise scheint die Site nur die Verwendung von -und ^innerhalb von Zeichenklassen zuzulassen ( ^kann also nicht als Anker verwendet werden), und eine Übereinstimmung wird nur gezählt, wenn die gesamte Zeichenfolge mit dem regulären Ausdruck übereinstimmt (dh eine implizite Umgebung ^$, z im Gegensatz zu normalen "regulären Ausdrücken", die eine Zeichenfolge als übereinstimmend zählen, wenn ein Teil davon mit dem
regulären Ausdruck
Als solches habe ich meine PCRE-Antwort gelöscht, die zwar auch in PHP funktionieren sollte, in diesem Fall aber fast definitiv nicht beabsichtigt ist.
Sp3000
Ich habe vergessen zu sagen, dass die Site prüft, ob der Ausdruck durch die Ereg-Funktion von PHP gültig ist. Es wurde in der Diskussion in ohjelmointiputka.net/keskustelu/…
Gast

Antworten:

6

204 Zeichen

(K((O(R(O(NKORO)*(NK(O(RK)?)?)?)?)?)?K)*(O(R(O(NKORO)*(N(K(O(RK?[^KO]|[^KR])|[^KO])|[^K])|[^KN])|[^KO])|[^KR])|[^KO])|[^K])*(K((O(R(O(NKORO)*(NK(O(RK)?)?)?)?)?)?K)*(O(R(O(NKORO)*(N(K(O(RK?)?)?)?)?)?)?)?)?

Erzeugt durch Verwandeln .*KORONKORKO.*in eine endliche Zustandsmaschine, Invertieren der endlichen Zustandsmaschine und Zurückverwandeln in einen regulären Ausdruck.

orlp
quelle
Warum wurde dies die beste Antwort?
Bálint
1

Python, 77 79 97 118 Bytes

Edit 3: Rewrite. Verwendet verschachtelte Lookaheads

^([^K]|K(?=$|[^O]|O(?=$|[^R]|R(?=$|[^O]|O(?=$|[^N]|N(?=$|[^K]|K(?=$|[^O]|O(?=$|[^R]|R(?=$|[^K]|K(?=$|[^O]))))))))))*$

Regex 101

Bearbeiten 2: '$ |' hinzugefügt im gesamten regulären Ausdruck. Wenn nun ein Präfix von KORONKORKO abgeglichen wurde, ist das nächste übereinstimmende Element das Ende der Zeichenfolge, ein Zeichen, das das Präfix beendet, oder ein Zeichen, das das Präfix erweitert, wenn darauf etwas folgt, das das Präfix beendet.

Dieser reguläre Ausdruck funktioniert mit re.fullmatch(), der in Python 3.4 hinzugefügt wurde. Zur Verwendung mit re.match(), ^und $Bedarf hinzugefügt werden zu Beginn und am Ende des Musters, jeweils für 2 weiteres Bytes.

([^K]|K($|[^O]|O($|[^R]|R($|[^O]|O($|[^N]|N($|[^K]|K($|[^O]|O($|[^R]|R($|[^K]|K($|[^O]))))))))))*

Regex101 Link

Vorherige falsche Lösung (siehe Kommentare):

K|([^K]|K([^O]|O([^R]|R([^O]|O([^N]|N([^K]|K([^O]|O([^R]|R([^K]|K[^O])))))))))*

Edit: Single K hinzugefügt

RootTwo
quelle
2
Ich glaube nicht, dass das passt K.
Orlp
@orip - Guter Fang. Fest.
RootTwo
Das letzte Update schlägt jetzt fehl fürKKORONKORKO
Sp3000
Ist es reparabel? Irgendwelche Ideen?
RootTwo
1
Der Anfang ^und das Ende $sind nicht notwendig. Auch =und $sind nicht erlaubt.
LegionMammal978