Supprimez toutes les occurrences de mots d'une chaîne donnée à l'aide de l'algorithme Z

Cet article se penche sur un problème intéressant de manipulation de chaînes : "Supprimer toutes les occurrences de mots d'une chaîne donnée à l'aide de l'algorithme Z". Ce problème est un bon cas d’application de l’algorithme Z dans les problèmes de recherche de modèles, soulignant son efficacité. Explorons cela en détail.

Énoncé du problème

Étant donné une chaîne S et un mot W, la tâche consiste à supprimer toutes les occurrences de W de S à l'aide de l'algorithme Z.

Comprendre le problème

Considérons une chaîne S = "HelloWorldHelloWorld" et un mot W = "World". Le but est de supprimer toutes les occurrences de W de S. Par conséquent, le résultat sera « HelloHello ».

Algorithme Z

L'algorithme Z peut trouver toutes les occurrences d'un motif dans le texte en temps linéaire. Il construit un tableau (tableau Z) où pour un index donné i, Z[i] représente la longueur de la sous-chaîne la plus longue commençant par i, qui est également le préfixe de la chaîne.

Méthode algorithmique

Voici les étapes pour résoudre le problème -

• Créez une nouvelle chaîne P = W + '$' + S.

• Appliquez l'algorithme Z à P et construisez le tableau Z.

• Parcourez le tableau Z. Si Z[i] est égal à la longueur de W, cela signifie que W existe à cet index. Supprimez W de S à cet index.

La traduction chinoise de

Exemple

est :

Exemple

Il s'agit d'un code C++ qui implémente la méthode ci-dessus :

#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;
}

Sortie

String after removal: Iam

Exemple de cas de test

Prenons un exemple -

Supposons S = "J'écris", W = "écrire". Le programme imprimera "Je suis". Les raisons sont les suivantes −

• La nouvelle chaîne P devient "writing$Iamwritingwriting".

• Après avoir appliqué l'algorithme Z, nous constatons que Z[8] et Z[15] sont égaux à la longueur de W, ce qui signifie que W existe à ces indices dans S.

  李>

• Ensuite, nous supprimons le W dans ces indices de S et obtenons la chaîne "Iam".

Conclusion

L'algorithme Z est un outil puissant pour résoudre les problèmes de recherche de modèles. Dans cet article, nous avons vu son application pour supprimer toutes les occurrences de mots d’une chaîne. Cette question est un excellent exemple des avantages de la compréhension et de l’application d’algorithmes de correspondance de chaînes. N’oubliez jamais que la compréhension et l’apprentissage des algorithmes ouvrent la voie à la résolution de problèmes complexes.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!