Как заменить подстроку строки

Опубликовано: 22 Сентября, 2022

Даны три строки S , S1 и S2 , состоящие из N , M и K символов соответственно, задача состоит в том, чтобы изменить строку S , заменив все подстроки S1 строкой S2 в строке S.

Примеры:

Input: S = “abababa”, S1 = “aba”, S2 = “a”
Output: aba
Explanation:
Change the substrings S[0, 2] and S[4, 6](= S1) to the string S2(= “a”) modifies the string S to “aba”. Therefore, print “aba”.

Input: S = “geeksforgeeks”, S1 = “eek”, S2 = “ok”
Output: goksforgoks

Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы пройти по строке S и, когда любая строка S1 будет найдена как подстрока в строке S , заменить ее на S2 . Выполните следующие шаги, чтобы решить эту проблему:

  • Инициализировать строку и сохранить результирующую строку после замены всех вхождений подстроки от S1 до S2 в строке S .
  • Переберите символы строки S , используя переменную i , и выполните следующие шаги:
    • Если префиксная подстрока строки S равна S1 из индекса i , то добавляем строку S2 в строку ans .
    • В противном случае добавьте текущий символ в строку ans .
  • После выполнения вышеуказанных шагов выведите строку an в качестве результата.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*M)
Вспомогательное пространство: O(N)

Эффективный подход. Описанный выше подход также можно оптимизировать, создав самый длинный правильный массив префиксов и суффиксов для строки S1 , а затем выполнив алгоритм KMP для поиска вхождений строки S1 в строке S. Выполните следующие шаги, чтобы решить эту проблему:

  • Создайте вектор, скажем, lps[] , который хранит самый длинный правильный префикс и суффикс для каждого символа, и заполните этот вектор, используя алгоритм KMP для строки S1 .
  • Инициализируйте две переменные, скажем, i и j как 0 , чтобы сохранить позицию текущего символа в s и s1 соответственно.
  • Инициализируйте найденный вектор для хранения всех начальных индексов, из которых строка S1 встречается в S .
  • Переберите символы строки S , используя переменную i , и выполните следующие шаги:
    • Если S[i] равно S1[j] , то увеличьте i и j на 1.
    • Если j равно длине s1 , то добавьте значение (i – j) к найденному вектору и обновите j как lps[j – 1] .
    • В противном случае, если значение S[i] не равно S1[j] , тогда, если j равно 0 , тогда увеличьте значение i на 1 . В противном случае обновите j как lps[j – 1] .
  • Инициализируйте переменную, скажем, prev как 0 , чтобы сохранить последний измененный индекс и пустую строку и сохранить результирующую строку после замены всех начальных появления s1 на s2 в s.
  • Пройдите по вектору found[] и, если значение found[i] больше, чем prev , добавьте строку S2 вместо S1 в ans .
  • После выполнения вышеуказанных шагов выведите строку an в качестве результата.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N + M)
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ