Der Text von Alice im Wunderland enthält das Wort " Wunderland '8 mal. (Lassen Sie uns für diese Frage nicht zwischen Groß- und Kleinschreibung unterscheiden).
Allerdings enthält es das Wort viel öfter, wenn Sie nicht zusammenhängende Teilfolgen sowie Teilzeichenfolgen zählen, zB
Entweder war der Brunnen sehr tief oder sie fiel sehr langsam, denn sie hatte es getan viel Zeit, als sie hinunterging, um nach ihr zu sehen und nach WONDER was war wird als nächstes passieren. Zuerst versuchte sie L ook down UND was heraus zu finden Sie kam, aber es war zu dunkel, um etwas zu sehen;
(Eine Teilsequenz ist eine Sequenz, die von einer anderen Sequenz abgeleitet werden kann, indem einige Elemente gelöscht werden, ohne die Reihenfolge der übrigen Elemente zu ändern. -Wikipedia)
Wie oft enthält das Buch das Wort Wunderland als Teilfolge? Ich erwarte, dass dies eine große Zahl sein wird - es ist ein langes Buch mit vielen w's und o's und n's und d's.
Ich habe das Brute-Force-Zählen (Rekursion, um eine Schleife 10 tief zu machen) versucht, aber es war zu langsam, sogar für diesen Beispiel-Absatz.
Die Zeichenkette "Wunderland" kommt als Teilfolge in Alice im Wunderland 1 24100772180603281661684131458232 mal vor .
Die Hauptidee besteht darin, den Haupttext Zeichen für Zeichen zu scannen und dabei zu zählen, wie oft jedes Präfix der Zielzeichenfolge lautet (dh in diesem Fall "w", "wo", "gewonnen", ..). ., "Wonderlan" und "Wunderland") ist bis zu dem aktuellen Brief aufgetreten. Diese laufenden Zahlen sind einfach zu berechnen und zu aktualisieren. Wenn der aktuelle Buchstabe in "Wunderland" nicht vorkommt, bleiben die Zählwerte unberührt. Wenn der aktuelle Buchstabe "a" ist, erhöhen wir die Zählung von "wonderla" s gesehen durch die Anzahl von "wonderl" s gesehen zu diesem Punkt. Wenn der aktuelle Buchstabe "n" ist, erhöhen wir die Zählung von "won" s um die Zählung von "wo" und die Zählung von "wonderlan" s um die Anzahl von "wonderla" s. Und so weiter. Wenn wir das Ende des Textes erreicht haben, werden wir alle Präfixe von "Wunderland" einschließlich der Zeichenfolge "Wunderland" selbst, wie gewünscht, haben.
Der Vorteil dieses Ansatzes ist, dass er einen einzigen Durchlauf durch den Text erfordert und keine O (n) rekursiven Aufrufe erfordert (die wahrscheinlich die maximale Rekursionstiefe überschreiten, wenn Sie nicht etwas Cleveres tun).
Nehmen wir an, Sie wollten nicht nach wonderland , sondern nur nach w suchen. Dann würden Sie einfach zählen, wie oft w in der Geschichte aufgetreten ist.
Nehmen wir nun an, Sie möchten wo . Für jedes erste Zeichen des aktuellen Musters, das Sie finden, fügen Sie Ihrer Zählung Folgendes hinzu:
Wie oft das aktuelle Muster ohne sein erstes Zeichen im Rest der Geschichte nach dem Charakter, in dem Sie sich befinden, auftritt: Sie haben das Problem (story[1..n], pattern[1..n]) auf (story[2..n], pattern[2..n])
Wie oft erscheint das gesamte aktuelle Muster im Rest der Geschichte? Sie haben das Problem also auf (story[2..n], pattern[1..n])
Jetzt können Sie einfach die beiden hinzufügen. Es gibt keine Überzählen, wenn wir in Teilproblemen sprechen. Betrachten Sie das Beispiel wawo . Offensichtlich kommt wo 2 mal vor. Sie könnten denken, dass das Zählen wie folgt abläuft:
Fügen Sie für die erste w 1 hinzu, weil o einmal danach und eine weitere 1 auftritt, weil wo einmal danach auftritt.
Fügen Sie für die zweite w 1 hinzu, da o einmal danach auftritt.
Antwort ist 3 , was falsch ist.
Aber genau das passiert tatsächlich:
%Vor% Sie können also sehen, dass die Antwort 2 ist.
Wenn Sie w nicht finden, ist die Anzahl für diese Position, wie oft wo nach diesem aktuellen Zeichen auftritt.
Dies ermöglicht eine dynamische Programmierung mit Memo:
%Vor% Aufruf mit count(0, 0, dp) . Beachten Sie, dass Sie den Code sauberer machen können (entfernen Sie den doppelten Funktionsaufruf).
Python-Code, ohne Memo:
%Vor%Ausgabe:
%Vor% Das macht Sinn: Für jedes i erste Zeichen in der ersten wonderland der Geschichte kannst du es mit den verbleibenden endgültigen Charakteren im zweiten wonderland gruppieren, was dir 10 solutions gibt. Ein weiteres 2 sind die Wörter selbst. Die anderen fünf sind:
Sie haben Recht, dass dies eine riesige Zahl sein wird. Ich schlage vor, dass Sie entweder große Ganzzahlen verwenden oder das Ergebnis modulo etwas nehmen.
Das gleiche Programm gibt 9624 für Ihren Beispielabsatz zurück.
Wenn Sie nach früheren Kommentaren suchen, wenn Sie nach einem Algorithmus suchen, der 2 für die Eingabe wonderlandwonderland und 1 für wonderwonderland zurückgibt, dann könnten Sie den Algorithmus aus dieser Frage anpassen:
So finden Sie kleinste Teilzeichenfolge, die alle Zeichen aus einer gegebenen Zeichenfolge enthält?
Effektiv wäre die Änderung in Ihrem Fall, dass Sie, sobald eine Instanz des Wortes gefunden wurde, einen Zähler erhöhen und den gesamten Vorgang mit dem restlichen Teil des Textes wiederholen.
Dieser Algorithmus wäre O(n) in der Zeit, wenn n die Länge des Textes und O(m) im Leerzeichen ist, wobei m die Länge der gesuchten Zeichenfolge ist.