Ich habe zwei algorithmische Fragen für ein Projekt, an dem ich gerade arbeite. Ich habe darüber nachgedacht und habe einige Vermutungen, aber ich würde auch gerne die Meinung der Community hören.
-
Angenommen, ich habe eine Zeichenkette und eine Liste von N regulären Ausdrücken (eigentlich sind es Platzhaltermuster, die eine Teilmenge der vollen Regex-Funktionalität darstellen). Ich möchte wissen, ob die Zeichenkette mit mindestens einem der regulären Ausdrücke in der Liste übereinstimmt. Gibt es eine Datenstruktur, mit der ich die Zeichenkette mit der Liste der regulären Ausdrücke in sublinearer (vermutlich logarithmischer) Zeit abgleichen kann?
-
Dies ist eine Erweiterung des vorherigen Problems. Nehmen wir an, ich habe die gleiche Situation: eine Zeichenkette und eine Liste von N regulären Ausdrücken, nur dass jetzt jeder der regulären Ausdrücke mit einem Offset innerhalb der Zeichenkette gepaart ist, an dem die Übereinstimmung beginnen muss (oder, wenn Sie es vorziehen, muss jeder der regulären Ausdrücke mit einer Teilzeichenkette der gegebenen Zeichenkette übereinstimmen, die am gegebenen Offset beginnt).
Ein Beispiel: Nehmen wir an, ich hätte die Zeichenfolge:
This is a test string
und die Regex-Muster und Offsets:
(a) his.\* at offset 0
(b) his.\* at offset 1Der Algorithmus sollte true zurückgeben. Obwohl Regex (a) nicht mit der Zeichenkette übereinstimmt, die bei Offset 0 beginnt, stimmt Regex (b) mit der Teilzeichenkette überein, die bei Offset 1 beginnt ("his is a test string").
Gibt es eine Datenstruktur, mit der ich dieses Problem in sublinearer Zeit lösen kann?
Eine möglicherweise nützliche Information ist, dass viele der Offsets in der Liste der regulären Ausdrücke oft gleich sind (d.h. oft passen wir die Teilzeichenkette an Offset X viele Male). Dies kann nützlich sein, um die Lösung des obigen Problems Nr. 1 zu nutzen.
Vielen Dank im Voraus für alle Vorschläge, die Sie haben!
