Entfernen Sie mithilfe des Z-Algorithmus alle Vorkommen von Wörtern aus einer bestimmten Zeichenfolge

Dieser Artikel befasst sich mit einem interessanten Problem der Zeichenfolgenmanipulation: „Entfernen Sie alle Vorkommen von Wörtern aus einer bestimmten Zeichenfolge mithilfe des Z-Algorithmus“. Dieses Problem ist ein guter Anwendungsfall des Z-Algorithmus bei Mustersuchproblemen und unterstreicht seine Wirksamkeit. Lassen Sie uns dies im Detail untersuchen.

Problemstellung

Bei einer gegebenen Zeichenfolge S und einem Wort W besteht die Aufgabe darin, mithilfe des Z-Algorithmus alle Vorkommen von W aus S zu entfernen.

Das Problem verstehen

Stellen Sie sich eine Zeichenfolge S = „HelloWorldHelloWorld“ und ein Wort W = „World“ vor. Das Ziel besteht darin, alle Vorkommen von W aus S zu entfernen. Daher lautet die Ausgabe „HelloHello“.

Z-Algorithmus

Der Z-Algorithmus kann alle Vorkommen eines Musters im Text in linearer Zeit finden. Es erstellt ein Array (Z-Array), wobei für einen gegebenen Index i Z[i] die Länge des längsten Teilstrings ab i darstellt, der auch das Präfix des Strings ist.

Algorithmusmethode

Hier sind die Schritte zur Lösung des Problems -

• Erstellen Sie eine neue Zeichenfolge P = W + '$' + S.

• Wenden Sie den Z-Algorithmus auf P an und erstellen Sie das Z-Array.

• Iterieren Sie über das Z-Array. Wenn Z[i] gleich der Länge von W ist, bedeutet dies, dass W an diesem Index existiert. Entfernen Sie W von S an diesem Index.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

Dies ist ein C++-Code, der die obige Methode implementiert:

#include<bits/stdc++.h>
using namespace std;

vector<int> constructZArray(string str) {
   int n = str.length();
   vector<int> Z(n, 0);
   int L = 0, R = 0;
   for (int i = 1; i < n; i++) {
      if (i > R) {
         L = R = i;
         while (R < n && str[R - L] == str[R])
               R++;
         Z[i] = R - L;
         R--;
      } else {
         int k = i - L;
         if (Z[k] < R - i + 1)
               Z[i] = Z[k];
         else {
               L = i;
               while (R < n && str[R - L] == str[R])
                  R++;
               Z[i] = R - L;
               R--;
         }
      }
   }
   return Z;
}

string removeWord(string S, string W) {
   string P = W + '$' + S;
   int len_W = W.length();
   vector<int> Z = constructZArray(P);
   vector<bool> toRemove(S.size(), false);
   for (int i = len_W + 1; i < Z.size(); i++) {
      if (Z[i] == len_W)
         fill(toRemove.begin() + i - len_W - 1, toRemove.begin() + i - 1, true);
   }
   
   string result = "";
   for (int i = 0; i < S.size(); i++) {
      if (!toRemove[i])
         result += S[i];
   }
   return result;
}

int main() {
   string S, W;
   S="Iamwritingwriting";
   W = "writing";
   cout << "String after removal: " << removeWord(S, W);
   return 0;
}

Ausgabe

String after removal: Iam

Testfallbeispiel

Lassen Sie uns ein Beispiel betrachten -

Angenommen, S = „Ich schreibe“ und W = „Schreiben“. Das Programm gibt „Iam“ aus. Die Gründe sind wie folgt: −

• Die neue Zeichenfolge P wird zu „writing$Iamwritingwriting“.

• Nach der Anwendung des Z-Algorithmus stellen wir fest, dass Z[8] und Z[15] gleich der Länge von W sind, was bedeutet, dass W an diesen Indizes in S existiert.

  李>

• Dann entfernen wir das W in diesen Indizes von S und erhalten die Zeichenfolge „Iam“.

Fazit

Der Z-Algorithmus ist ein leistungsstarkes Werkzeug zur Lösung von Mustersuchproblemen. In diesem Artikel haben wir seine Anwendung beim Entfernen aller Vorkommen von Wörtern aus einer Zeichenfolge gesehen. Diese Frage ist ein gutes Beispiel für die Vorteile des Verständnisses und der Anwendung von String-Matching-Algorithmen. Denken Sie immer daran, dass das Verstehen und Erlernen von Algorithmen Möglichkeiten zur Lösung komplexer Probleme eröffnet.

Das obige ist der detaillierte Inhalt vonEntfernen Sie mithilfe des Z-Algorithmus alle Vorkommen von Wörtern aus einer bestimmten Zeichenfolge. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!