Dadas dos strings S1 y S2 . La tarea es envolver cada instancia de la string S2 en la string S1 con alguna string a cada lado.
Nota: Aquí usaremos un guión bajo (_) para la parte de envolver. Puede ser cualquier cosa según la necesidad, por ejemplo, alguna etiqueta HTML , espacio en blanco, etc.
Ejemplos:
Entrada: S1 = «examenserá un examenexamen», S2 = «examen»
Salida: «_examen_será un _examenexamen_»
Explicación:
la string S2 es » examen «, por lo que envuelva la aparición de S2 con un guión bajo. Dado que las dos últimas ocurrencias se superponen (en la string examexam ), fusione tanto la ocurrencia como el ajuste colocando un guión bajo más a la izquierda y más a la derecha de la substring fusionada.
Entrada: str = “abcabcabcabc”, substr = “abc”
Salida: “_abcabcabcabc_”
Enfoque: la idea es simplemente obtener la ubicación de todas las instancias de la string S2 en S1 y agregar un guión bajo en cualquier extremo de la ocurrencia y, si dos o más instancias de S2 se superponen, agregue un guión bajo en cualquier extremo de la substring combinada. A continuación se muestran los pasos:
- Obtenga la ubicación de todas las instancias de la string S2 en la string principal S1 . Para esa string transversal S1 un carácter a la vez y llame a la función de coincidencia de substrings, find() .
- Cree una array 2D de ubicaciones (digamos arr[][] ), donde cada subarreglo contiene los índices inicial y final de una instancia específica de la string S2 en la string S1 .
- Combine los intervalos de índice de inicio y finalización superpuestos almacenados en arr[][].
- Después de los pasos anteriores, todos los índices superpuestos se fusionan. Ahora recorra la string y los intervalos dados al mismo tiempo y cree una nueva string envolviendo guiones bajos.
- Imprima la nueva string después del paso anterior.
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 Definitions
vector<vector<int> > getLocations(string str,
string subStr);
vector<vector<int> > collapse(
vector<vector<int> > locations);
string underscorify(string str,
vector<vector<int> > locations);
// Function that creates the string by
// wrapping the underscore
string underscorifySubstring(string str,
string subStr)
{
// Function Call to intervals of
// starting and ending index
vector<vector<int> > locations
= collapse(getLocations(str, subStr));
// Function Call
return underscorify(str, locations);
}
// Function finds all starting and ending
// index of the substring in given string
vector<vector<int> > getLocations(string str,
string subStr)
{
vector<vector<int> > locations{};
int startIdx = 0;
int L = subStr.length();
// Traverse string str
while (startIdx < str.length()) {
// Find substr
int nextIdx = str.find(subStr,
startIdx);
// If location found, then insert
// pair int location[]
if (nextIdx != string::npos) {
locations.push_back({ nextIdx,
(nextIdx + L) });
// Update the start index
startIdx = nextIdx + 1;
}
else {
break;
}
}
return locations;
}
// Function to merge the locations
// of substrings that overlap each
// other or sit next to each other
vector<vector<int> > collapse(
vector<vector<int> > locations)
{
if (locations.empty()) {
return locations;
}
// 2D vector to store the merged
// location of substrings
vector<vector<int> > newLocations{ locations[0] };
vector<int>* previous = &newLocations[0];
for (int i = 1; i < locations.size(); i++) {
vector<int>* current = &locations[i];
// Condition to check if the
// substring overlaps
if (current->at(0) <= previous->at(1)) {
previous->at(1) = current->at(1);
}
else {
newLocations.push_back(*current);
previous
= &newLocations[newLocations.size() - 1];
}
}
return newLocations;
}
// Function creates a new string with
// underscores added at correct positions
string underscorify(string str,
vector<vector<int> > locations)
{
int locationsIdx = 0;
int stringIdx = 0;
bool inBetweenUnderscores = false;
vector<string> finalChars{};
int i = 0;
// Traverse the string and check
// in locations[] to append _
while (stringIdx < str.length()
&& locationsIdx < locations.size()) {
if (stringIdx
== locations[locationsIdx][i]) {
// Insert underscore
finalChars.push_back("_");
inBetweenUnderscores
= !inBetweenUnderscores;
// Increment location index
if (!inBetweenUnderscores) {
locationsIdx++;
}
i = i == 1 ? 0 : 1;
}
// Create string s
string s(1, str[stringIdx]);
// Push the created string
finalChars.push_back(s);
stringIdx++;
}
if (locationsIdx < locations.size()) {
finalChars.push_back("_");
}
else if (stringIdx < str.length()) {
finalChars.push_back(str.substr(stringIdx));
}
// Return the resultant string
return accumulate(finalChars.begin(),
finalChars.end(), string());
}
// Driver Code
int main()
{
// Given string S1 and S2
string S1 = "examwill be a examexam";
string S2 = "exam";
// Function Call
cout << underscorifySubstring(S1, S2);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
// Function that creates the string by
// wrapping the underscore
static String underscorifySubstring(String str,
String subStr)
{
// Function Call to intervals of
// starting and ending index
List<List<Integer> > locations
= collapse(getLocations(str, subStr));
// Function Call
return underscorify(str, locations);
}
// Function finds all starting and ending
// index of the substring in given string
static List<List<Integer> > getLocations(String str,
String subStr)
{
@SuppressWarnings("unchecked")
List<List<Integer> > locations = new ArrayList();
int startIdx = 0;
int L = subStr.length();
// Traverse string str
while (startIdx < str.length())
{
// Find substr
int nextIdx = str.indexOf(subStr, startIdx);
// If location found, then insert
// pair int location[]
if (nextIdx != -1)
{
locations.add(Arrays.asList(new Integer[] {
nextIdx, nextIdx + L }));
// Update the start index
startIdx = nextIdx + 1;
}
else
{
break;
}
}
return locations;
}
// Function to merge the locations
// of substrings that overlap each
// other or sit next to each other
static List<List<Integer> >
collapse(List<List<Integer> > locations)
{
if (locations.size() == 0)
{
return locations;
}
// 2D vector to store the merged
// location of substrings
@SuppressWarnings("unchecked")
List<List<Integer> > newLocations = new ArrayList();
newLocations.add(locations.get(0));
List<Integer> previous = locations.get(0);
for (int i = 1; i < locations.size(); i++)
{
List<Integer> current = locations.get(i);
// Condition to check if the
// substring overlaps
if (current.get(0) <= previous.get(1))
{
previous.set(1, current.get(1));
}
else
{
newLocations.add(current);
previous = newLocations.get(
newLocations.size() - 1);
}
}
return newLocations;
}
// Function creates a new string with
// underscores added at correct positions
static String
underscorify(String str, List<List<Integer> > locations)
{
int locationsIdx = 0;
int stringIdx = 0;
boolean inBetweenUnderscores = false;
StringBuilder finalChars = new StringBuilder();
int i = 0;
// Traverse the string and check
// in locations[] to append _
while (stringIdx < str.length()
&& locationsIdx < locations.size()) {
if (stringIdx
== locations.get(locationsIdx).get(i)) {
// Insert underscore
finalChars.append("_");
inBetweenUnderscores
= !inBetweenUnderscores;
// Increment location index
if (!inBetweenUnderscores)
{
locationsIdx++;
}
i = i == 1 ? 0 : 1;
}
// Push the string
finalChars.append(str.charAt(stringIdx));
stringIdx++;
}
if (locationsIdx < locations.size()) {
finalChars.append("_");
}
else if (stringIdx < str.length()) {
finalChars.append(str.substring(stringIdx));
}
// Return the resultant string
return finalChars.toString();
}
public static void main(String[] args)
{
// Given string S1 and S2
String S1 = "examwill be a examexam";
String S2 = "exam";
// Function Call
System.out.print(underscorifySubstring(S1, S2));
}
}
// This code is contributed by jithin
Producción:
_exam_will be a _examexam_
Complejidad temporal: O(N * M), donde N y M son la longitud de la string S1 y S2 respectivamente.
Espacio auxiliar: O(N), donde N es la longitud de la string S1