Aufgabe
Die Aufgabe besteht darin, einen exakten String-Matching-Algorithmus Ihrer Wahl in Echtzeit zu entwickeln.
Eingang
Zwei Textzeilen in der Standardeingabe, durch eine neue Zeile getrennt. Die erste Zeile enthält das "Muster" und ist einfach eine ASCII-Zeichenfolge, die aus den Buchstaben gezogen wird a-z
.
Die zweite Zeile enthält den längeren "Text" und ist einfach eine ASCII-Zeichenfolge, die aus den Buchstaben gezogen wird a-z
.
Ausgabe
Eine Liste der Indizes, bei denen die genauen Übereinstimmungen auftreten. Sie sollten die Position des Starts jedes auftretenden Matches ausgeben.
Spezifikation
Ihr Algorithmus kann die Vorverarbeitung des Musters in linearer Zeit durchführen. Es muss dann den Text von links nach rechts lesen und für jedes einzelne Zeichen im Text eine konstante Zeit benötigen und jede neue Übereinstimmung ausgeben, sobald sie auftritt. Übereinstimmungen können sich natürlich überlappen.
Algorithmus
Es gibt viele Echtzeit-Algorithmen für den exakten Abgleich. Eine wird zum Beispiel im Wiki für KMP erwähnt . Sie können jede beliebige Antwort verwenden, aber Sie müssen immer die richtige Antwort ausgeben.
Ich werde einen pro Sprache führenden Tisch führen, damit diejenigen, die beliebte Sprachen bevorzugen, auch auf ihre eigene Weise gewinnen können. Bitte erläutern Sie, welchen Algorithmus Sie implementiert haben.
Echtzeit
Es scheint viel Verwirrung darüber zu geben, was Echtzeit bedeutet. Es bedeutet nicht einfach lineare Zeit. Standard-KMP ist also nicht in Echtzeit. Der Link in der Frage verweist explizit auf einen Teil der Wiki-Seite für KMP über eine Echtzeit-Variante von KMP. Boyer-Moore-Galil ist auch nicht in Echtzeit. In dieser theoretischen Frage / Antwort wird das Problem erörtert, oder man kann einfach "Echtzeit- Exaktabstimmung " oder ähnliche Begriffe googeln.
quelle
abcd
und hätteacbdefg
, würde ich ausgeben1 4
, füra
undd
?a
als auchd
passend. Es gibtabcd
undacbdefg
, und diea
undd
sind an identischen Positionen.Antworten:
Python 2, 495 Bytes
Dies ist ein Echtzeit-KMP, der viel kürzer und nur geringfügig langsamer ist als der BMG-Algorithmus (der normalerweise sublinear ist). Rufen Sie an mit
K(pattern, text)
; Die Ausgabe ist identisch mit dem BMG-Algorithmus.quelle
Python 2, 937 Bytes
Das ist keineswegs kurz, aber es (a) funktioniert, (b) erfüllt alle Anforderungen und (c) wird so viel Golf gespielt, wie ich nur kann.
Dies ist eine Implementierung des Boyer-Moore-Galil-Algorithmus. Ziemlich unkompliziert - rufen Sie mit
S(pattern,text)
; Die anderen beiden Funktionen werden in der Vorverarbeitung verwendet. Tatsächlich wird alles außer den letzten 5 Zeilen vorverarbeitet.Ein Beispiellauf, der ungefähr eine Sekunde dauerte:
quelle
O(m)
Preprocessing undO(n)
Matching [=>O(n+m)
] ausgeführt werden muss, was dies tut (oder besser).O(n+m)
pünktlich ablaufen, aber n Zeit für eines der Symbole im Text, zum Beispiel.KMP, Python 2 (213 Byte)
Ungolfed-Version. Die erste Schleife besteht darin, die KMP-Automaten aufzubauen. Die zweite Schleife läuft auf den Automaten. Sie haben fast dasselbe Muster, aber das Abstrahieren kostet mehr Bytes. Für einen Code-Golf würde ich diese Logik lieber duplizieren. Eine ähnliche Implementierung wird häufig in Programmierwettbewerben verwendet.
quelle
Echtzeit-KMP, Python 2 (167 Byte)
Im normalen KMP simulieren wir das Automatenverhalten mit einer Fail-Funktion. In diesem Echtzeit-KMP ist der Vollautomat so aufgebaut, dass er in der passenden Phrase jedes Zeichen in Echtzeit (konstante Zeit) verarbeiten kann.
Die zeitliche und räumliche Komplexität der Vorverarbeitung beträgt O (nm), wobei m die Alphabetgröße und n die Länge der Musterfolge ist. In meinen Tests ist die tatsächliche Größe der Übergangstabelle jedoch immer kleiner als 2n, sodass wir möglicherweise nachweisen können, dass die zeitliche und räumliche Komplexität O (n) ist.
Ungolfed-Version
quelle
Q, 146 Bytes
Prüfung
erzeugt 15 und 34
Anmerkungen
Nicht auf das Alphabet beschränkt (unterstützt alle ASCII-Zeichen und unterscheidet zwischen Groß- und Kleinschreibung).
Verwendet keine der spezifischen Operationen, die von Q für Zeichenfolgen definiert wurden -> arbeitet mit Zeichenfolgen als Sequenzen (Ops-Übereinstimmung, Länge usw.)
Minimiert die Übergangstabelle, die alle Zeichen, die nicht im Muster enthalten sind, zu einer eindeutigen Zeichenklasse zusammenfügt.
Ich kann Code ein wenig drücken. Es ist ein erster Versuch, die Lösungsstrategie zu validieren
Besuchen Sie ein beliebiges Textzeichen genau einmal, und für jedes eingegebene Zeichen gibt es einen eindeutigen Sprung. Ich gehe also davon aus, dass die Suche als "Echtzeit" passt.
Die Tabellenkonstruktion al state i und char c suchen nach der längsten Teilzeichenfolge, die bei i endet, und nach dem Anhängen von c ist ein Präfix von S. Die Konstruktion ist nicht optimiert, daher weiß ich nicht, ob sie gültig ist
Das Eingabeformat passt nicht gut zur Sprache. Wenn Sie zwei Zeichenfolgenargumente übergeben, werden 16 Byte gespart
Erläuterung
globales W steht für Muster und S entspricht dem zu suchenden Text
x:1_"\n "\:x
Seltsamer Code, um die Eingabeanforderungen zu erfüllen (Q erfordert, dass mehrzeilige Zeichenfolgen eingerückte Nicht-Erste-Zeilen aufweisen, sodass zusätzlicher Speicherplatz vor jeder Nicht-Erste-Zeile verworfen werden muss)n::#W
berechnet W länge und speichert als globales nu::?W
berechnet eindeutige Zeichen in W und speichert sie als globales uu?S
generiert die characted-Klasse für jedes Zeichen von SErstellen Sie eine Übergangstabelle T mit einer Zeile pro eindeutigem Zeichen in W (plus einer zusätzlichen) und einer Spalte für jeden Index in W (plus einer zusätzlichen). Zusätzliche Zeile entspricht dem Anfangszustand, und zusätzliche Spalte sammelt Zeichen in S, jedoch nicht in W. Diese Strategie minimiert die Tabellengröße
p:{$[n<#x;0;x~(#x)#W;#x;0]}
ist die Funktion, die nach dem längsten Präfix suchtf:{{|/p'x}'((1_)\x#W),\:/:u}
ist die Funktion, die eine Zeile x von T berechnetSuchen Sie den Text mit der Übergangstabelle.
T\[0;u?S]
iteriert über 0 (Anfangszustand) und jede der Zeichenklassen von S und verwendet als neuen Wert den Wert in der Übergangstabelle T [Zustand] [charClass]. Der Endzustand hat den Wert n, also suchen wir diesen Wert in der Folge der Zustände und geben ihn angepasst zurück (um die anfängliche anstelle der endgültigen Position jeder Übereinstimmung anzugeben).quelle
Boyer-Moore, Perl (50)
Perl versucht Boyer-Moore auf natürliche Weise zu nutzen:
quelle