Wer weiß, wie man einen Suchbaum an begrenzte reguläre Ausdrücke anpassen kann? Die Aufgabe besteht darin, bei einem Dateinamen alle Knoten zu finden, die mit diesem Dateinamen übereinstimmen. Knoten können übliche Dateinamen enthalten (* und?). Offensichtlich, da dies ein Suchbaum ist, ist Geschwindigkeit essentiell.Regulärer Ausdruck (Glob) Suchbaum
EDIT: Ich sollte hinzufügen, dass der wichtigste Fall für die Geschwindigkeit ist die durchschnittliche Zeit, um eine Übereinstimmung auszuschließen. Das heißt, in den meisten Fällen wird der Abgleich fehlschlagen.
Ein Beispiel: Angenommen, der Baum die folgenden Knoten enthalten:
foo, bar, foo *, * bar, foo
Suche nach foo bar würde Knoten zurück 1 und 3 bar für gesucht? würde Knoten 2 und 4 zurückgeben. Suche nach fob würde keine Knoten zurückgeben. Suche nach fooxbar würde Knoten 5 zurückgeben. Suche nach foobar würde Knoten 3 und 4 zurückgeben.
Ist dies ein umgekehrtes Problem (von Regex): Übereinstimmung, wenn eine Zeichenfolge zu einer regulären Sprache gehört oder nicht? – dirkgently
Können Sie uns einen Beispiel-E/A geben? – dirkgently
Ein Beispiel: Angenommen, der Baum enthielt die folgenden Knoten: foo, bar, foo *, * bar, foo? Bar Gegeben eine Zeichenfolge (zB foo, foobar, fooxbar, fob, etc.), schnell den Knoten finden (s), falls vorhanden, die dieser Zeichenfolge entsprechen. –