Dadas dos strings str de longitud N y palabra de longitud M , la tarea es eliminar todas las apariciones de la string word de la string str .
Ejemplos:
Entrada: str = “asmGeeksasmasmForasmGeeks”, palabra = “asm”
Salida: GeeksForGeeks
Explicación:
Eliminando “asm” de la string, str modifica str a GeeksForGeeksEntrada: str = “Z-kmalgorithmkmiskmkmkmhelpfulkminkmsearching”, palabra = “km”
Salida: Z-algorithmishelpfulinsearchingExplicación:
Eliminando «km» de la string, str modifica str a «Z-algorithmishelpfulinsearching».
Enfoque ingenuo: el enfoque más simple para resolver este problema es iterar sobre los caracteres de la string str . Para cada índice, verifique si se puede encontrar una substring cuyo índice inicial sea igual al índice actual y la substring sea igual a la string, palabra . Si se determina que es cierto, elimine la substring. Finalmente, imprima la string.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque basado en STL : elimine todas las ocurrencias de la palabra de string de la string str usando el método replace() .
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando el algoritmo Z. Siga los pasos a continuación para resolver el problema:
- Inicialice una string, digamos res , para almacenar la string eliminando las palabras de la string dada str .
- Inicialice una array , digamos Z[] , para almacenar el valor Z de la string.
- Encuentre todas las apariciones de la palabra de string en la string str dada usando el algoritmo Z.
- Finalmente, recorra la array Z[] y verifique si z[i + longitud (palabra) + 1] es igual a longitud (palabra) o no. Si se determina que es cierto, actualice i += length(word) – 1 .
- De lo contrario, agregue el carácter actual a la string res .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to fill the Z-array for str
void getZarr(string str, int Z[])
{
int n = str.length();
int k;
// L Stores start index of window
// which matches with prefix of str
int L = 0;
// R Stores end index of window
// which matches with prefix of str
int R = 0;
// Iterate over the characters of str
for (int i = 1; i < n; ++i) {
// If i is greater thn R
if (i > R) {
// Update L and R
L = R = i;
// If substring match with prefix
while (R < n && str[R - L] == str[R]) {
// Update R
R++;
}
// Update Z[i]
Z[i] = R - L;
// Update R
R--;
}
else {
// Update k
k = i - L;
// if Z[k] is less than
// remaining interval
if (Z[k] < R - i + 1) {
// Update Z[i]
Z[i] = Z[k];
}
else {
// Start from R and check manually
L = i;
while (R < n && str[R - L] == str[R]) {
// Update R
R++;
}
// Update Z[i]
Z[i] = R - L;
// Update R
R--;
}
}
}
}
// Function to remove all the occurrences
// of word from str
string goodStr(string str, string word)
{
// Create concatenated string "P$T"
string concat = word + "$" + str;
int l = concat.length();
// Store Z array of concat
int Z[l];
getZarr(concat, Z);
// Stores string, str by removing all
// the occurrences of word from str
string res;
// Stores length of word
int pSize = word.size();
// Traverse the array, Z[]
for (int i = 0; i < l; ++i) {
// if Z[i + pSize + 1] equal to
// length of word
if (i + pSize < l - 1 && Z[i + pSize + 1] == pSize) {
// Update i
i += pSize - 1;
}
else if (i < str.length()) {
res += str[i];
}
}
return res;
}
// Driver Code
int main()
{
string str
= "Z-kmalgorithmkmiskmkmkmhelpfulkminkmsearching";
string word = "km";
cout << goodStr(str, word);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to fill the Z-array for str
static void getZarr(String str, int Z[])
{
int n = str.length();
int k;
// L Stores start index of window
// which matches with prefix of str
int L = 0;
// R Stores end index of window
// which matches with prefix of str
int R = 0;
// Iterate over the characters of str
for (int i = 1; i < n; ++i)
{
// If i is greater thn R
if (i > R)
{
// Update L and R
L = R = i;
// If subString match with prefix
while (R < n && str.charAt(R - L) ==
str.charAt(R))
{
// Update R
R++;
}
// Update Z[i]
Z[i] = R - L;
// Update R
R--;
}
else
{
// Update k
k = i - L;
// if Z[k] is less than
// remaining interval
if (Z[k] < R - i + 1)
{
// Update Z[i]
Z[i] = Z[k];
}
else
{
// Start from R and check manually
L = i;
while (R < n && str.charAt(R - L) ==
str.charAt(R))
{
// Update R
R++;
}
// Update Z[i]
Z[i] = R - L;
// Update R
R--;
}
}
}
}
// Function to remove all the occurrences
// of word from str
static String goodStr(String str, String word)
{
// Create concatenated String "P$T"
String concat = word + "$" + str;
int l = concat.length();
// Store Z array of concat
int []Z = new int[l];
getZarr(concat, Z);
// Stores String, str by removing all
// the occurrences of word from str
String res="";
// Stores length of word
int pSize = word.length();
// Traverse the array, Z[]
for (int i = 0; i < l; ++i) {
// if Z[i + pSize + 1] equal to
// length of word
if (i + pSize < l - 1 && Z[i + pSize + 1] == pSize) {
// Update i
i += pSize - 1;
}
else if (i < str.length()) {
res += str.charAt(i);
}
}
return res;
}
// Driver Code
public static void main(String[] args)
{
String str
= "Z-kmalgorithmkmiskmkmkmhelpfulkminkmsearching";
String word = "km";
System.out.print(goodStr(str, word));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 program for the above approach # Function to fill the Z-array for str def getZarr(st, Z): n = len(st) k = 0 # L Stores start index of window # which matches with prefix of str L = 0 # R Stores end index of window # which matches with prefix of str R = 0 # Iterate over the characters of str for i in range(1, n): # If i is greater thn R if (i > R): # Update L and R L = R = i # If substring match with prefix while (R < n and st[R - L] == st[R]): # Update R R += 1 # Update Z[i] Z[i] = R - L # Update R R -= 1 else: # Update k k = i - L # if Z[k] is less than # remaining interval if (Z[k] < R - i + 1): # Update Z[i] Z[i] = Z[k] else: # Start from R and check manually L = i while (R < n and st[R - L] == st[R]): # Update R R += 1 # Update Z[i] Z[i] = R - L # Update R R -= 1 # Function to remove all the occurrences # of word from str def goodStr(st, word): # Create concatenated string "P$T" concat = word + "$" + st l = len(concat) # Store Z array of concat Z = [0]*l getZarr(concat, Z) # Stores string, str by removing all # the occurrences of word from str res = "" # Stores length of word pSize = len(word) # Traverse the array, Z[] for i in range(l): # if Z[i + pSize + 1] equal to # length of word if (i + pSize < l - 1 and Z[i + pSize + 1] == pSize): # Update i i += pSize - 1 elif (i < len(st)): res += st[i] return res # Driver Code if __name__ == "__main__": st = "Z-kmalgorithmkmiskmkmkmhelpfulkminkmsearching" word = "km" print(goodStr(st, word)) # This code is contributed by chitranayal.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to fill the Z-array for str
static void getZarr(string str, int[] Z)
{
int n = str.Length;
int k;
// L Stores start index of window
// which matches with prefix of str
int L = 0;
// R Stores end index of window
// which matches with prefix of str
int R = 0;
// Iterate over the characters of str
for (int i = 1; i < n; ++i)
{
// If i is greater thn R
if (i > R)
{
// Update L and R
L = R = i;
// If subString match with prefix
while (R < n && str[R - L] ==
str[R])
{
// Update R
R++;
}
// Update Z[i]
Z[i] = R - L;
// Update R
R--;
}
else
{
// Update k
k = i - L;
// if Z[k] is less than
// remaining interval
if (Z[k] < R - i + 1)
{
// Update Z[i]
Z[i] = Z[k];
}
else
{
// Start from R and check manually
L = i;
while (R < n && str[R - L] ==
str[R])
{
// Update R
R++;
}
// Update Z[i]
Z[i] = R - L;
// Update R
R--;
}
}
}
}
// Function to remove all the occurrences
// of word from str
static string goodStr(string str, string word)
{
// Create concatenated String "P$T"
string concat = word + "$" + str;
int l = concat.Length;
// Store Z array of concat
int []Z = new int[l];
getZarr(concat, Z);
// Stores String, str by removing all
// the occurrences of word from str
string res="";
// Stores length of word
int pSize = word.Length;
// Traverse the array, Z[]
for (int i = 0; i < l; ++i) {
// if Z[i + pSize + 1] equal to
// length of word
if (i + pSize < l - 1 && Z[i + pSize + 1] == pSize) {
// Update i
i += pSize - 1;
}
else if (i < str.Length) {
res += str[i];
}
}
return res;
}
// Driver Code
static public void Main()
{
string str
= "Z-kmalgorithmkmiskmkmkmhelpfulkminkmsearching";
string word = "km";
Console.WriteLine(goodStr(str, word));
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
//js program for the above approach
// Function to fill the Z-array for str
function getZarr(str,Z)
{
let n = str.length;
let k;
// L Stores start index of window
// which matches with prefix of str
let L = 0;
// R Stores end index of window
// which matches with prefix of str
let R = 0;
// Iterate over the characters of str
for (let i = 1; i < n; ++i)
{
// If i is greater thn R
if (i > R)
{
// Update L and R
L = R = i;
// If subString match with prefix
while (R < n && str[R - L] ==
str[R])
{
// Update R
R++;
}
// Update Z[i]
Z[i] = R - L;
// Update R
R--;
}
else
{
// Update k
k = i - L;
// if Z[k] is less than
// remaining interval
if (Z[k] < R - i + 1)
{
// Update Z[i]
Z[i] = Z[k];
}
else
{
// Start from R and check manually
L = i;
while (R < n && str[R - L] ==
str[R])
{
// Update R
R++;
}
// Update Z[i]
Z[i] = R - L;
// Update R
R--;
}
}
}
}
// Function to remove all the occurrences
// of word from str
function goodStr(str,word)
{
// Create concatenated String "P$T"
let concat = word + "$" + str;
let l = concat.length;
// Store Z array of concat
let Z = new Array(l);
getZarr(concat, Z);
// Stores String, str by removing all
// the occurrences of word from str
let res="";
// Stores length of word
let pSize = word.length;
// Traverse the array, Z[]
for (let i = 0; i < l; ++i) {
// if Z[i + pSize + 1] equal to
// length of word
if (i + pSize < l - 1 && Z[i + pSize + 1] == pSize) {
// Update i
i += pSize - 1;
}
else if (i < str.length) {
res += str[i];
}
}
return res;
}
// Driver Code
let str = "Z-kmalgorithmkmiskmkmkmhelpfulkminkmsearching";
let word = "km";
document.write(goodStr(str, word));
</script>
Producción:
Z-algorithmishelpfulinsearching
Complejidad temporal: O(N + M)
Espacio auxiliar: O(N)