Remove all occurrences of words from a given string using Z algorithm

This article delves into an interesting string manipulation problem: "Removing all occurrences of words from a given string using the Z algorithm". This problem is a good application case of the Z algorithm in pattern search problems, highlighting its effectiveness. Let’s explore this in detail.

Problem Statement

Given a string S and a word W, the task is to remove all occurrences of W from S using the Z algorithm.

Understanding Questions

Consider a string S = "HelloWorldHelloWorld" and a word W = "World". The goal is to remove all occurrences of W from S. Therefore, the output will be "HelloHello".

Z-Algorithm

The Z algorithm can find all occurrences of a pattern in text in linear time. It constructs an array (Z array) where for a given index i, Z[i] represents the length of the longest substring starting from i, which is also the prefix of the string.

Algorithm method

Here are the steps to solve the problem -

• Create a new string P = W '$' S.

• Apply the Z algorithm to P and construct the Z array.

• Iterate over the Z array. If Z[i] is equal to the length of W, it means that W exists at that index. Remove W from S at that index.

The Chinese translation of

Example

is:

Example

This is a C code that implements the above method:

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

Output

String after removal: Iam

Test case example

Let us consider an example -

Assume S = "Iamwritingwriting", W = "writing". The program will print "Iam". The reasons are as follows −

• The new string P becomes "writing$Iamwritingwriting".

• After applying the Z algorithm, we find that Z[8] and Z[15] are equal to the length of W, which means that W exists at these indices in S.

  李>

• Then we remove the W in these indices from S and get the string "Iam".

in conclusion

Z Algorithms are powerful tools for solving pattern search problems. In this article, we saw its application in removing all occurrences of words from a string. This question is a great example of the benefits of understanding and applying string matching algorithms. Always remember that understanding and learning algorithms opens up ways to solve complex problems.

The above is the detailed content of Remove all occurrences of words from a given string using Z algorithm. For more information, please follow other related articles on the PHP Chinese website!