4

Remove all occurrences of a string t in string s using Boyer-Moore Algorithm

 1 year ago
source link: https://www.geeksforgeeks.org/remove-all-occurrences-of-a-string-t-in-string-s-using-boyer-moore-algorithm//
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Remove all occurrences of a string t in string s using Boyer-Moore Algorithm

Given a string s and string t, the task is to remove all occurrences of a string t in a string s using the Boyer-Moore algorithm.

Examples:

Input: s = “ababaababa”, t = “aba” 
Output: baab 

Input: s = “Geeksforgeeks”, t = “eek”
Output: Gsforgs

Approach: This can be solved with the following idea:

  • We initialize the bad character rule and then loop through s using the Boyer-Moore algorithm to find all occurrences of . When we find a match, we remove the matched substring from s.
  • In the preBadChar() function we create an array called badChar[] that stores the index of the last occurrence of each character in t. This is called the “bad character rule”, and it allows the algorithm to skip over some characters in s that do not match t. We then define the removeOccurrences function.

Below are the steps involved in the implementation of the code:

  • We first calculate the lengths of the input strings s and t and initialize the badChar array of size 256 with all elements set to -1. The badChar array will be used to store the index of the last occurrence of each character in the pattern t.
  • We then call the preBadChar() function which populates the badChar array with the index of the last occurrence of each character in the pattern t.
  • We initialize the variable i to 0, which will be used to keep track of the index of the start of the window of s that we will compare to the pattern t.
  • We start a while loop that will continue until i is less than or equal to n – m, where n is the length of s and m is the length of t. This ensures that we don’t go past the end of the s string while searching for occurrences of t.
  • Inside the while loop, we initialize the variable j to m – 1. This will be used to keep track of the index of the end of the window of s that we will compare to the pattern t. We start from the end of the pattern and compare it to the corresponding characters in s starting from index i + j.
  • We then start another while loop which will compare the characters in the pattern t with the corresponding characters in s. We will continue to compare the characters until either we have matched all the characters in t with the corresponding characters in s, or until we find a character in t that doesn’t match the corresponding character in s.
  • If we have matched all the characters in t, we have found an occurrence of t in s. We remove the matched substring from s using the erase() function and update the value of n to reflect the new length of s. We then update the value of i to skip over the matched substring.
  • If we didn’t match all the characters in t, we have found a mismatch. We calculate the index of the bad character in s using the badChar array. If the bad character doesn’t exist in t, we can skip over the entire window of s. Otherwise, we move the window to the right by the maximum of 1 and j minus the index of the bad character in s. This allows us to skip over some unnecessary comparisons and potentially find the next occurrence of t faster.
  • We repeat steps 5-8 until we have searched through the entire s string.
  • Finally, the modified s string with all occurrences of t removed is returned.

Below is the implementation of the above approach:

// C++ Implementation
#include <bits/stdc++.h>
#define NO_OF_CHARS 256
using namespace std;
void preBadChar(string t, int m, int badChar[])
{
int i;
for (i = 0; i < NO_OF_CHARS; i++) {
badChar[i] = -1;
}
for (i = 0; i < m; i++) {
badChar[(int)t[i]] = i;
}
}
// Function to remove occurrence of string
void removeOccurrences(string& s, string t)
{
int m = t.length();
int n = s.length();
int badChar[NO_OF_CHARS];
preBadChar(t, m, badChar);
int i = 0;
while (i <= n - m) {
int j = m - 1;
while (j >= 0 && t[j] == s[i + j]) {
j--;
}
if (j < 0) {
s.erase(i, m);
n = s.length();
i += m;
}
else {
i += max(1, j - badChar[s[i + j]]);
}
}
}
// Driver code
int main()
{
string s = "Geeksforgeeks";
string t = "eek";
// Function call
removeOccurrences(s, t);
cout << s << endl;
return 0;
}
Output
Gsforgs

Time Complexity: O(mn)
Auxiliary Space: O(k)


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK