Hier ist mein Ansatz zur Lösung des obigen Problems.
1 . Nehmen Sie 2 Zeiger Kopf und Schwanz zeigen beide auf 0
Bewegen Sie nun den Kopfzeiger, bis das Wort, auf das der Kopfzeiger zeigt, ein gültiges Schlüsselwort ist; markieren Sie es nun als Kopf.
2 . Bewegen Sie nun den Schwanzzeiger, bis der Satz alle angegebenen Schlüsselwörter mindestens einmal enthält; markieren Sie ihn nun als Schwanz.
Und dies ist das erste gültige Teilsegment mit allen gültigen Schlüsselwörtern, dessen Länge berechnet wird
3 . Prüfen Sie nun die Worthäufigkeit am Kopf - wenn sie größer als 1 ist, bewegen Sie den Kopfzeiger zu einem Wort im Satz, das ein gültiges Schlüsselwort ist und eine Worthäufigkeit von 1 enthält.
4 . Prüfen Sie nun, ob alle Schlüsselwörter vorhanden sind oder nicht - wenn ja, berechnen Sie die Länge und speichern Sie sie als minimales Teilsegment.
5 . Wenn er nicht alle gültigen Schlüsselwörter enthält, bewegen Sie den Zeiger auf den Schwanz, bis alle Schlüsselwörter gefunden wurden, und berechnen Sie seine Länge wie (Schwanz-Kopf+1); wenn er größer als mindestens eins ist, ignorieren Sie ihn.
6 . Fahren Sie nun mit diesem Vorgang bis zum letzten Schlüsselwort des Satzes fort
Die Komplexität des obigen Ansatzes ist o(n).
Nehmen wir zum Beispiel diesen Satz
Hi this is a funny world this is a good experience with this world
und ich muss 3 Schlüsselwörter finden
this
is
world
Betrachten Sie zunächst 2 Hash-Tabellen, und zwar erforderliche und erhaltene Speichern Sie nun alle benötigten Schlüsselwörter in der Tabelle required.
Nehmen Sie nun Kopf und Schwanz als 0 und prüfen Sie, ob hi ein gültiges Schlüsselwort ist, da es den Kopf nicht bewegt
Nun suchen Sie nach dem nächsten Schlüsselwort, d.h. diesem, jetzt ist dies ein gültiges Schlüsselwort, also zählen Sie 1 und speichern Sie diese Wortposition als Kopf.
Bewegen Sie nun den Zeiger so, dass das nächste Schlüsselwort "is" ist, es ist ein gültiges Schlüsselwort, daher wird die Anzahl erhöht. Jetzt in ähnlicher Weise nach a,funny Schlüsselwörtern suchen, da sie nicht gültig sind, und den Zeiger auf world verschieben
jetzt ist world ein gültiges, da count 3 und tail 4 ist, wenn count == no of required keywords (in unserem Fall ist es 3), was bedeutet, dass unser Segment alle gültigen Keywords enthält
Die Länge ist nun (4-1+1)=4
Prüfen Sie nun die Häufigkeit des Wortes am Kopf, es ist eins, wenn wir also den Kopfzeiger verschieben, erhalten wir kein gültiges Segment
Bewegen Sie nun den Schwanzzeiger zum nächsten Wort und aktualisieren Sie die Frequenz von 1 auf 2 und der Zähler wird zu 4
Jetzt können wir unseren Kopfzeiger auf ein Schlüsselwort verschieben und den Zähler auf 3 aktualisieren, da unser Segment dies in diesem Moment nicht enthalten wird, da wir den Kopfzeiger von diesem Schlüsselwort verschoben haben
Jetzt ist die Anzahl wieder 3, also berechne die Länge wieder 4.
Prüfen Sie also die Frequenz des Hauptschlüsselworts, es ist 1, und bewegen Sie den Schwanzzeiger zum nächsten Schlüsselwort, jetzt ist die Frequenz des Schlüsselworts größer als 1, und bewegen Sie den Kopfzeiger, bis wir ein gültiges Schlüsselwort mit einer Frequenz von 1 erhalten, das jetzt Welt heißt und die Kopfposition 5 und die Schwanzposition 7 ist. und der Zähler ist 3, also berechnen Sie die Länge als 7-5+1, was 3 ist, und das ist die minimale Länge, die wir bis jetzt gefunden haben
verschieben Sie nun den Schwanz, bis die Keyword-Frequenz am Kopf größer als 1 ist, so dass unser Schwanz schließlich 13 wird
Bewege nun den Kopf von 5 nach 6 und berechne seine Länge, und es wird 13-6+1, was 8 ist, also ignoriere es
jetzt können wir unseren Schwanz nicht mehr verschieben, also drucken wir die Wörter von min_head bis min_tail als Endergebnis
in unserem Fall lautet die Antwort
Diese Welt ist
