Dadas tres strings S , S1 y S2 que constan de N , M y K caracteres respectivamente, la tarea es modificar la string S reemplazando todas las substrings S1 con la string S2 en la string S .
Ejemplos:
Entrada: S = “abababa”, S1 = “aba”, S2 = “a”
Salida: aba
Explicación:
Cambie las substrings S[0, 2] y S[4, 6](= S1) a la string S2(= “a”) modifica la string S a “aba”. Por lo tanto, escriba «aba».Entrada: S = «geeksforgeeks», S1 = «eek», S2 = «ok»
Salida: goksforgoks
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es atravesar la string S y cuando cualquier string S1 se encuentre como una substring en la string S , reemplácela por S2 . Siga los pasos a continuación para resolver este problema:
- Inicialice una string y almacene la string resultante después de reemplazar todas las ocurrencias de la substring S1 a S2 en la string S .
- Iterar sobre los caracteres de la string S usando la variable i y realizar los siguientes pasos:
- Después de completar los pasos anteriores, imprima la string como resultado.
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 replace all the occurrences
// of the substring S1 to S2 in string S
void modifyString(string& s, string& s1,
string& s2)
{
// Stores the resultant string
string ans = "";
// Traverse the string s
for (int i = 0; i < s.length(); i++) {
int k = 0;
// If the first character of
// string s1 matches with the
// current character in string s
if (s[i] == s1[k]
&& i + s1.length()
<= s.length()) {
int j;
// If the complete string
// matches or not
for (j = i; j < i + s1.length(); j++) {
if (s[j] != s1[k]) {
break;
}
else {
k = k + 1;
}
}
// If complete string matches
// then replace it with the
// string s2
if (j == i + s1.length()) {
ans.append(s2);
i = j - 1;
}
// Otherwise
else {
ans.push_back(s[i]);
}
}
// Otherwise
else {
ans.push_back(s[i]);
}
}
// Print the resultant string
cout << ans;
}
// Driver Code
int main()
{
string S = "geeksforgeeks";
string S1 = "eek";
string S2 = "ok";
modifyString(S, S1, S2);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to replace all the occurrences
// of the subString S1 to S2 in String S
static void modifyString(String s, String s1, String s2)
{
// Stores the resultant String
String ans = "";
// Traverse the String s
for (int i = 0; i < s.length(); i++) {
int k = 0;
// If the first character of
// String s1 matches with the
// current character in String s
if (s.charAt(i) == s1.charAt(k)
&& i + s1.length() <= s.length()) {
int j;
// If the complete String
// matches or not
for (j = i; j < i + s1.length(); j++) {
if (s.charAt(j) != s1.charAt(k)) {
break;
}
else {
k = k + 1;
}
}
// If complete String matches
// then replace it with the
// String s2
if (j == i + s1.length()) {
ans += (s2);
i = j - 1;
}
// Otherwise
else {
ans += (s.charAt(i));
}
}
// Otherwise
else {
ans += (s.charAt(i));
}
}
// Print the resultant String
System.out.print(ans);
}
// Driver Code
public static void main(String[] args)
{
String S = "geeksforgeeks";
String S1 = "eek";
String S2 = "ok";
modifyString(S, S1, S2);
}
}
// This code is contributed by gauravrajput1
C#
// C# program for the above approach
using System;
public class GFG {
// Function to replace all the occurrences
// of the subString S1 to S2 in String S
static void modifyString(String s, String s1, String s2)
{
// Stores the resultant String
String ans = "";
// Traverse the String s
for (int i = 0; i < s.Length; i++) {
int k = 0;
// If the first character of
// String s1 matches with the
// current character in String s
if (s[i] == s1[k]
&& i + s1.Length <= s.Length) {
int j;
// If the complete String
// matches or not
for (j = i; j < i + s1.Length; j++) {
if (s[j] != s1[k]) {
break;
}
else {
k = k + 1;
}
}
// If complete String matches
// then replace it with the
// String s2
if (j == i + s1.Length) {
ans += (s2);
i = j - 1;
}
// Otherwise
else {
ans += (s[i]);
}
}
// Otherwise
else {
ans += (s[i]);
}
}
// Print the resultant String
Console.Write(ans);
}
// Driver Code
public static void Main(String[] args)
{
String S = "geeksforgeeks";
String S1 = "eek";
String S2 = "ok";
modifyString(S, S1, S2);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program for the above approach
// Function to replace all the occurrences
// of the sublet S1 to S2 in let S
function modifylet(s, s1,
s2)
{
// Stores the resultant let
let ans = "";
// Traverse the let s
for (let i = 0; i < s.length; i++) {
let k = 0;
// If the first character of
// let s1 matches with the
// current character in let s
if (s[i] == s1[k]
&& i + s1.length
<= s.length) {
let j;
// If the complete let
// matches or not
for (j = i; j < i + s1.length; j++) {
if (s[j] != s1[k]) {
break;
}
else {
k = k + 1;
}
}
// If complete let matches
// then replace it with the
// let s2
if (j == i + s1.length) {
ans = ans + s2;
i = j - 1;
}
// Otherwise
else {
ans = ans + s[i];
}
}
// Otherwise
else {
ans = ans + s[i];
}
}
// Print the resultant let
document.write(ans);
}
// Driver Code
let S = "geeksforgeeks";
let S1 = "eek";
let S2 = "ok";
modifylet(S, S1, S2);
// This code is contributed by splevel62.
</script>
Producción:
goksforgoks
Complejidad temporal: O(N*M)
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior también se puede optimizar creando la array de prefijos y sufijos adecuada más larga para la string S1 y luego realizar el algoritmo KMP para encontrar las ocurrencias de la string S1 en la string S . Siga los pasos a continuación para resolver este problema:
- Cree un vector , digamos lps[] que almacene el prefijo y el sufijo adecuados más largos para cada carácter y complete este vector usando el algoritmo KMP para la string S1 .
- Inicialice dos variables, digamos, i y j como 0 para almacenar la posición del carácter actual en s y s1 respectivamente.
- Inicialice un vector encontrado para almacenar todos los índices iniciales a partir de los cuales aparece la string S1 en S .
- Iterar sobre los caracteres de la string S usando la variable i y realizar los siguientes pasos:
- Si S[i] es igual a S1[j] , entonces incremente i y j en 1.
- Si j es igual a la longitud de s1 , agregue el valor (i – j) al vector encontrado y actualice j como lps[j – 1] .
- De lo contrario, si el valor de S[i] no es igual a S1[j] , entonces si j es igual a 0 , entonces incremente el valor de i en 1 . De lo contrario, actualice j como lps[j – 1] .
- Inicialice una variable, por ejemplo, anterior como 0 para almacenar el último índice modificado y una string vacía y ans para almacenar la string resultante después de reemplazar todas las apariencias iniciales de s1 por s2 en s.
- Atraviese el vector found[] y si el valor de found[i] es mayor que prev , agregue la string S2 en lugar de S1 en ans .
- Después de completar los pasos anteriores, imprima la string como resultado.
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 calculate the LPS array
// for the given string S1
vector<int> computeLPS(string& s1)
{
// Stores the longest proper prefix
// and suffix for each character
// in the string s1
vector<int> lps(s1.length());
int len = 0;
// Set lps value 0 for the first
// character of the string s1
lps[0] = 0;
int i = 1;
// Iterate to fill the lps vector
while (i < s1.length()) {
if (s1[i] == s1[len]) {
len = len + 1;
lps[i] = len;
i = i + 1;
}
else {
// If there is no longest
// proper prefix which is
// suffix, then set lps[i] = 0
if (len == 0) {
lps[i] = 0;
i = i + 1;
}
// Otherwise
else
len = lps[len - 1];
}
}
return lps;
}
// Function to replace all the occurrences
// of the substring S1 to S2 in string S
void modifyString(string& s, string& s1,
string& s2)
{
vector<int> lps = computeLPS(s1);
int i = 0;
int j = 0;
// Stores all the starting index
// from character S1 occurs in S
vector<int> found;
// Iterate to find all starting
// indexes and store all indices
// in a vector found
while (i < s.length()) {
if (s[i] == s1[j]) {
i = i + 1;
j = j + 1;
}
// The string s1 occurrence is
// found and store it in found[]
if (j == s1.length()) {
found.push_back(i - j);
j = lps[j - 1];
}
else if (i < s.length()
&& s1[j] != s[i]) {
if (j == 0)
i = i + 1;
else
j = lps[j - 1];
}
}
// Stores the resultant string
string ans = "";
int prev = 0;
// Traverse the vector found[]
for (int k = 0; k < found.size(); k++) {
if (found[k] < prev)
continue;
ans.append(s.substr(prev, found[k] - prev));
ans.append(s2);
prev = found[k] + s1.size();
}
ans.append(s.substr(prev,
s.length() - prev));
// Print the resultant string
cout << ans << endl;
}
// Driver Code
int main()
{
string S = "geeksforgeeks";
string S1 = "eek";
string S2 = "ok";
modifyString(S, S1, S2);
return 0;
}
Producción:
goksforgoks
Complejidad temporal: O(N + M)
Espacio auxiliar: O(N)