Geben Sie für ein Wort und einen Text die Anzahl der Vorkommen von Anagrammen des Wortes im Text zurück. Für z. Wort ist "für" und der Text ist "forxxorfxdofr", Anagramme von "für" werden "ofr", "orf", "fro" usw. Also wäre die Antwort für dieses spezielle Beispiel 3.
Ich habe den Brute-Force-Ansatz, der alle Permutationen des Wortes bekommt, dann vergleiche, ob der Text es enthält, und die Anzahl der Vorkommen erhöhen, aber das ist O (N ^ 2) Ansatz. Ich suche eine bessere Komplexität.
Sie können einfach nach der Anzahl der Zeichen suchen.
Sagen Sie zum Beispiel, dass Sie nach Anagrammen von look suchen. Also, du suchst:
Verarbeiten Sie einfach die ersten 4 Buchstaben, speichern Sie die Zählungen. Überprüfen Sie, ob Sie eine Übereinstimmung haben. Addiere das nächste Zeichen (Inkrement), entferne das alte Zeichen (Dekrement). Nochmal Überprüfen. Und so weiter ...
TooTones O ( n ) Lösung leidet unter dem Vergleich zweier Vektoren mit je 256 Elementen für jedes Zeichen des Eingabetextes. Dies kann vermieden werden, indem die Anzahl der Positionen verfolgt wird, bei denen sich die zwei Vektoren unterscheiden, und eine Übereinstimmung registriert wird, wenn diese Zahl auf Null geht. Tatsächlich müssen wir nicht einmal zwei verschiedene Vektoren speichern, da wir einfach einen Vektor speichern können, der ihre Differenz enthält.
Hier ist meine Version, die diese Optimierungen implementiert. Es ist in reinem alten C geschrieben, sollte aber unter C ++ mit entsprechenden Anpassungen funktionieren:
%Vor%Im Wesentlichen können Sie ein Fenster mit der Länge Ihres Wortes über Ihre Eingabe schieben und zählen, wie viele Buchstaben in dem Fenster sind. Wenn der Buchstabe in Ihrem gleitenden Fenster mit den Buchstabenzahlen Ihres Wortes übereinstimmt, haben Sie eine Übereinstimmung.
Lassen Sie Ihre Wortlänge n und Ihre aktuelle Position ist curr . Erstellen Sie ein Array oder vector , windCounts der Länge 26. Der Eintrag windCounts[i] speichert die Anzahl der Vorkommen des i th Buchstabens des Alphabets von Position curr - n - 1 bis curr .
Was Sie tun, ist, dass Sie curr vorrücken und Ihr Array windCounts auf dem neuesten Stand halten, indem Sie den Buchstaben, der aus der Rückseite des gleitenden Fensters herausgefallen ist, dekrementieren und die Anzahl der Buchstaben, die in vor dem Schiebefenster. (Natürlich, bis curr & gt; n , Sie nur erhöhen, bauen Sie einfach Ihr Schiebefenster auf die Länge Ihres Wortes.)
In C ++ können Sie vector für die Anzahl der Buchstaben in Ihrem Wort und für die Anzahl der Buchstaben in Ihrem gleitenden Fenster verwenden und einfach vector::operator== für die Gleichheit verwenden.
Bearbeiten : Der Algorithmus ist O(N) , wobei N die Länge des zu suchenden Texts ist. Dies wird aus dem folgenden Code ersichtlich, in dem der Schleifenkörper für jeden Buchstaben ausgeführt wird, den Sie in das Fenster schieben.
Ich habe zwei Strings genommen, nämlich str und occ. Str ist der ursprüngliche Strin und Occ ist der Stich, für den wir den Count herausfinden müssen. Mit der Funktion strncpy habe ich die Länge von occ, d. H. N Zeichen, in ein temp-Array kopiert und dann überprüft, ob es sich um eine Permutation der occ-Zeichenfolge handelt oder nicht.
%Vor%