Рубрики

На месте заменить несколько вхождений шаблона

Для данной строки и шаблона замените несколько вхождений шаблона на символ «X». Преобразование должно быть на месте, и решение должно заменить несколько последовательных (и не перекрывающихся) вхождений шаблона на один «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

Идея состоит в том, чтобы сохранить два индекса i и j для замены на месте. Индекс i всегда указывает на следующий символ в выходной строке. Индекс j пересекает строку и ищет одно или несколько совпадений с образцом. Если совпадение найдено, мы помещаем символ 'X' в индекс i и увеличиваем индекс i на 1, а индекс j — на длину шаблона. Индекс i увеличивается только один раз, если мы находим несколько последовательных вхождений шаблона. Если шаблон не найден, мы копируем текущий символ с индексом j в индекс i и увеличиваем i и j на 1. Поскольку длина шаблона всегда больше 1 и длина замены составляет всего 1 символ, мы никогда не перезаписываем необработанные символы т.е. j> = i является инвариантом.

// Программа на C ++ для замены на месте
// вхождения шаблона по символу 'X'
#include <bits/stdc++.h>

using namespace std;

  
// возвращает true, если pattern является префиксом str

bool compare(char* str, char* pattern)

{

    for (int i = 0; pattern[i]; i++)

        if (str[i] != pattern[i])

            return false;

    return true;

}

  
// Функция для замены нескольких
// вхождения шаблона по символу 'X'

void replacePattern(char* str, char* pattern)

{

    // Если шаблон является пустой или пустой строкой,

    // ничего не нужно делать

    if (pattern == NULL)

        return;

  

    int len = strlen(pattern);

    if (len == 0)

        return;

  

    int i = 0, j = 0;

    int count;

  

    // для каждого персонажа

    while (str[j]) {

        count = 0;

  

        // сравниваем str [j..j + len] с шаблоном

        while (compare(str + j, pattern)) {

            // увеличиваем j на длину шаблона

            j = j + len;

            count++;

        }

  

        // Если один или несколько вхождений шаблона

        // найдено, замените его символом 'X'

        if (count > 0)

            str[i++] = 'X';

  

        // копировать символ в текущей позиции j

        // для позиционирования i и увеличения i и j

        if (str[j])

            str[i++] = str[j++];

    }

  

    // добавить нулевой символ для завершения строки

    str[i] = '\0';

}

  
// Код драйвера

int main()

{

    char str[] = "GeeksforGeeks";

    char pattern[] = "Geeks";

  

    replacePattern(str, pattern);

    cout << str;

  

    return 0;

}

Выход:

XforX

Временная сложность вышеупомянутого алгоритма составляет O (n * m), где n — длина строки, а m — длина шаблона.

Реализация с использованием 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 ++ для замены на месте
// вхождения шаблона по символу 'X'
#include <bits/stdc++.h>

using namespace std;

  
// Функция для замены нескольких
// вхождения шаблона по символу 'X'

void replacePattern(string str, string pattern)

{

  

    // делаем итератор для строки str

    string::iterator it = str.begin();

    // запускаем этот цикл, пока итератор не достигнет конца строки

    while (it != str.end()) {

        // поиск первого индекса в строке str где

        // первое появление строкового шаблона

        it = search(str.begin(), str.end(), pattern.begin(), pattern.end());

        // проверка, не указывает ли итератор на конец

        // строка str

        if (it != str.end()) {

            // стираем полную строку шаблона из этого итератора

            // позиция в строке str

            str.erase(it, it + pattern.size());

            // вставляем 'X' в позицию итератора

            str.insert(it, 'X');

        }

    }

  

    // этот цикл удаляет последовательный 'X' в строке s

    // Пример: GeeksGeeksforGeeks был изменен на «XXforX»

    // выполнение этого цикла изменит его на 'XforX'

    for (int i = 0; i < str.size() - 1; i++) {

        if (str[i] == 'X' && str[i + 1] == 'X') {

            // удаляем 'X' в позиции i в строке str

            str.erase(str.begin() + i);

            i--; // я-- потому что один символ был удален

            // так что я меняю

        }

    }

    cout << str;

}

  
// Код драйвера

int main()

{

    string str = "GeeksforGeeks";

    string pattern = "Geeks";

  

    replacePattern(str, pattern);

  

    return 0;

}

Выход:

XforX

Эта статья предоставлена Aditya Goel . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

На месте заменить несколько вхождений шаблона

0.00 (0%) 0 votes