Reemplazar en el lugar múltiples ocurrencias de un patrón

Dada una string y un patrón, reemplace múltiples ocurrencias de un patrón por el carácter ‘X’. La conversión debe estar en el lugar y la solución debe reemplazar múltiples ocurrencias consecutivas (y no superpuestas) de un patrón por una sola ‘X’ .

String – GeeksForGeeks
Pattern – Geeks
Output: XforX
 
String – GeeksGeeks
Pattern – Geeks
Output: X

String – aaaa
Pattern – aa
Output: X

String – aaaaa
Pattern – aa
Output: Xa

La idea es mantener dos índices i y j para el reemplazo en el lugar. El índice i siempre apunta al siguiente carácter en la string de salida. El índice j atraviesa la string y busca una o más coincidencias de patrón. Si se encuentra una coincidencia, colocamos el carácter ‘X’ en el índice i e incrementamos el índice i en 1 y el índice j en la longitud del patrón. El índice i se incrementa solo una vez si encontramos múltiples ocurrencias consecutivas del patrón. Si no se encuentra el patrón, copiamos el carácter actual en el índice j al índice i e incrementamos tanto i como j en 1. Dado que la longitud del patrón siempre es más que igual a 1 y el reemplazo tiene solo 1 carácter, nunca sobrescribiríamos los caracteres no procesados es decir, j >= i es invariante.

Implementación:

// C++ program to in-place replace multiple
// occurrences of a pattern by character ‘X’
#include <bits/stdc++.h>
using namespace std;
 
// returns true if pattern is prefix of str
bool compare(char* str, char* pattern)
{
    for (int i = 0; pattern[i]; i++)
        if (str[i] != pattern[i])
            return false;
    return true;
}
 
// Function to in-place replace multiple
// occurrences of a pattern by character ‘X’
void replacePattern(char* str, char* pattern)
{
    // If pattern is null or empty string,
    // nothing needs to be done
    if (pattern == NULL)
        return;
 
    int len = strlen(pattern);
    if (len == 0)
        return;
 
    int i = 0, j = 0;
    int count;
 
    // for each character
    while (str[j]) {
        count = 0;
 
        // compare str[j..j+len] with pattern
        while (compare(str + j, pattern)) {
            // increment j by length of pattern
            j = j + len;
            count++;
        }
 
        // If single or multiple occurrences of pattern
        // is found, replace it by character 'X'
        if (count > 0)
            str[i++] = 'X';
 
        // copy character at current position j
        // to position i and increment i and j
        if (str[j])
            str[i++] = str[j++];
    }
 
    // add a null character to terminate string
    str[i] = '\0';
}
 
// Driver code
int main()
{
    char str[] = "GeeksforGeeks";
    char pattern[] = "Geeks";
 
    replacePattern(str, pattern);
    cout << str;
 
    return 0;
}

# Python3 program to in-place replace multiple
# occurrences of a pattern by character ‘X’
 
# returns true if pattern is prefix of Str
def compare(Str, pattern):
 
    if(len(Str) != len(pattern)):
        return False
 
    for i in range(len(pattern)):
        if (Str[i] != pattern[i]):
            return False
         
    return True
 
# Function to in-place replace multiple
# occurrences of a pattern by character ‘X’
def replacePattern(Str,pattern):
 
    # If pattern is null or empty String,
    # nothing needs to be done
    if (pattern == ""):
        return
 
    Len = len(pattern)
 
    if (Len == 0):
        return
 
    i, j = 0, 0
 
    # for each character
    while (j < len(Str)):
 
        count = 0
 
        # compare Str[j..j+len] with pattern
        while (compare(Str[j:j+Len], pattern)):
            # increment j by length of pattern
            j = j + Len
            count += 1
 
        # If single or multiple occurrences of pattern
        # is found, replace it by character 'X'
        if (count > 0):
            Str = Str[0:i] + 'X' + Str[i+1:]
            i += 1
         
 
        # copy character at current position j
        # to position i and increment i and j
        if (j<len(Str)):
            Str = Str[0:i] + Str[j] + Str[i+1:]
            i += 1
            j += 1
 
    # add a null character to terminate String
    Str = Str[0:i]
    return Str
 
# Driver code
Str = "GeeksforGeeks"
pattern = "Geeks"
 
Str = replacePattern(Str, pattern)
print(Str)
 
# This code is contributed by shinjanpatra

<script>
 
// JavaScript program to in-place replace multiple
// occurrences of a pattern by character ‘X’
 
// returns true if pattern is prefix of str
function compare(str, pattern)
{
    for (let i = 0; i<pattern.length; i++)
        if (str[i] != pattern[i])
            return false;
    return true;
}
 
// Function to in-place replace multiple
// occurrences of a pattern by character ‘X’
function replacePattern(str,pattern)
{
    // If pattern is null or empty string,
    // nothing needs to be done
    if (pattern == "")
        return;
 
    let len = pattern.length;
    if (len == 0)
        return;
 
    let i = 0, j = 0;
    let count;
 
    // for each character
    while (j<str.length) {
 
        count = 0;
 
        // compare str[j..j+len] with pattern
        while (compare(str.substring(j,j+len), pattern)) {
            // increment j by length of pattern
            j = j + len;
            count++;
        }
 
        // If single or multiple occurrences of pattern
        // is found, replace it by character 'X'
        if (count > 0){
            str = str.substring(0,i) + 'X' + str.substring(i+1,)
            i++
        }
 
        // copy character at current position j
        // to position i and increment i and j
        if (j<str.length){
            str = str.substring(0,i) + str[j] + str.substring(i+1,)
            i++;j++
        }
    }
 
    // add a null character to terminate string
    str = str.substring(0,i);
    return str;
}
 
// Driver code
let str = "GeeksforGeeks";
let pattern = "Geeks";
 
str = replacePattern(str, pattern);
document.write(str,"</br>");
 
// This code is contributed by shinjanpatra
 
</script>

XforX

Complejidad de tiempo: O(n*m) donde n es la longitud de la string y m es la longitud del patrón.

Espacio Auxiliar: O(1) 

Implementación usando STL

The idea of this implementation is to use the STL in-built functions 
to search for pattern string in main string and then erasing it 
from the main string

// C++ program to in-place replace multiple
// occurrences of a pattern by character ‘X’
#include <bits/stdc++.h>
using namespace std;
 
// Function to in-place replace multiple
// occurrences of a pattern by character ‘X’
void replacePattern(string str, string pattern)
{
 
    // making an iterator for string str
    string::iterator it = str.begin();
    // run this loop until iterator reaches end of string
    while (it != str.end()) {
        // searching the first index in string str where
        // the first occurrence of string pattern occurs
        it = search(str.begin(), str.end(), pattern.begin(), pattern.end());
        // checking if iterator is not pointing to end of the
        // string str
        if (it != str.end()) {
            // erasing the full pattern string from that iterator
            // position in string str
            str.erase(it, it + pattern.size());
            // inserting 'X' at that iterator position
            str.insert(it, 'X');
        }
    }
 
    // this loop removes consecutive 'X' in string s
    // Example: GeeksGeeksforGeeks was changed to 'XXforX'
    // running this loop will change it to 'XforX'
    for (int i = 0; i < str.size() - 1; i++) {
        if (str[i] == 'X' && str[i + 1] == 'X') {
            // removing 'X' at position i in string str
            str.erase(str.begin() + i);
            i--; // i-- because one character was deleted
            // so repositioning i
        }
    }
    cout << str;
}
 
// Driver code
int main()
{
    string str = "GeeksforGeeks";
    string pattern = "Geeks";
 
    replacePattern(str, pattern);
 
    return 0;
}

XforX

Tiempo Complejidad: O(n*m)
Espacio Auxiliar: O(1)

Este artículo es una contribución de Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.