Dadas dos strings, text y pattern , de tamaño N y M (N > M) respectivamente, la tarea es imprimir todas las ocurrencias de pattern en text .
Ejemplos:
Entrada: texto = «Este es un texto ficticio», patrón = «Esto»
Salida: Patrón encontrado en índices: 0
Explicación: El patrón «Esto» comienza desde el índice 0 en el texto dado.Entrada: texto = «Bienvenido a Geeks para Geeks», patrón = «Geeks»
Salida: Patrón encontrado en los índices: 21 11
Explicación: El patrón «Geeks» comienza desde el índice 11 y 21 (considerando los espacios en blanco).
Enfoque: El enfoque para este problema se basa en la siguiente idea:
Encuentre los posibles índices iniciales de todos los puntos iniciales en el texto. Luego, para todos esos índices, verifique si sus adyacentes coinciden con los siguientes elementos del patrón.
La idea anterior se puede implementar usando la cola . Siga los pasos mencionados a continuación para implementar la idea.
- En primer lugar, use una array de tamaño 256 de unordered_set . Recorra el texto e inserte cada índice al conjunto del carácter respectivo.
C++
for (int i = 0; i < st.length(); i++) // Insert every index to the hash set using character // ASCII. structured_text[st[i]].insert(i);
- Busque el primer carácter del patrón en la array e inserte cada índice contenido en el conjunto hash en una cola .
C++
for (int ind : structured_text[pattern[0]]) q_indices.push(ind);
- Luego recorre el patrón desde i = 1 hasta M-1 :
- Si el índice en texto_estructurado[patrón[i]] es adyacente a cualquiera de los caracteres presentes en pat[i-1] , introdúzcalo en la cola para la próxima iteración.
- De lo contrario, continúe buscando otras posiciones.
C++
for (int i = 1; i < pattern.length(); i++) {
char ch = pattern[i];
int q_size = q_indices.size();
/* the queue contains the number of occurrences of the
previous character. traverse the queue for q_size times
Check the next character of the pattern found or not. */
while (q_size--) {
int ind = q_indices.front();
q_indices.pop();
if (structured_text[ch].find(ind + 1)
!= structured_text[ch].end())
q_indices.push(ind + 1);
}
}
- Si se encuentra el patrón completo, devuelva esos índices.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
// Using a 256 sized array of
// hash sets.
unordered_set<int> structured_text[256];
// Function to perform the hashing
void StringSearch(string st)
{
// Structure the text. It will be
// helpful in pattern searching
for (int i = 0; i < st.length(); i++)
// Insert every index to the
// hash set using character ASCII.
structured_text[st[i]].insert(i);
}
// Function to search the pattern
void pattern_search(string st, string pattern)
{
StringSearch(st);
// Queue contain the indices
queue<int> q_indices;
for (int ind : structured_text[pattern[0]])
q_indices.push(ind);
// Pattern length
int pat_len = pattern.length();
for (int i = 1; i < pat_len; i++) {
char ch = pattern[i];
int q_size = q_indices.size();
// The queue contains the
// number of occurrences of
// the previous character.
// Traverse the queue for
// q_size times.
// Check the next character of
// the pattern found or not.
while (q_size--) {
int ind = q_indices.front();
q_indices.pop();
if (structured_text[ch].find(ind + 1)
!= structured_text[ch].end())
q_indices.push(ind + 1);
}
}
cout << "Pattern found at indexes:";
while (!q_indices.empty()) {
// last_ind is the last index
// of the pattern in the text
int last_ind = q_indices.front();
q_indices.pop();
cout << " " << last_ind - (pat_len - 1);
}
cout << endl;
}
// Driver code
int main()
{
// Passing the Text
string text = "Welcome to Geeks for Geeks";
string pattern = "Geeks";
// Function call
pattern_search(text, pattern);
return 0;
}
Python3
# Python program for the above approach:
## Using a 256 sized array of
## hash sets.
structured_text = [set({}) for _ in range(256)]
## Function to perform the hashing
def StringSearch(st):
## Structure the text. It will be
## helpful in pattern searching
global structured_text
for i in range(len(st)):
## Insert every index to the
## hash set using character ASCII.
structured_text[ord(st[i])].add(i)
## Function to search the pattern
def pattern_search(st, pattern):
global structured_text
StringSearch(st)
## Queue contain the indices
q_indices = []
for ind in structured_text[ord(pattern[0])]:
q_indices.append(ind)
## Pattern length
pat_len = len(pattern);
for i in range(1, pat_len):
ch = pattern[i]
q_size = len(q_indices)
## The queue contains the
## number of occurrences of
## the previous character.
## Traverse the queue for
## q_size times.
## Check the next character of
## the pattern found or not.
while q_size > 0:
q_size -= 1
ind = q_indices[0]
q_indices.pop(0)
if ((ind + 1) in structured_text[ord(ch)]):
q_indices.append(ind + 1)
print("Pattern found at indexes:", end="")
while len(q_indices) > 0:
## last_ind is the last index
## of the pattern in the text
last_ind = q_indices[0]
q_indices.pop(0)
print("", last_ind - (pat_len - 1), end="")
print("")
## Driver code
if __name__ == '__main__':
## Passing the Text
text = "Welcome to Geeks for Geeks"
pattern = "Geeks"
## Function call
pattern_search(text, pattern)
# This code is contributed by subhamgoyal2014.
Pattern found at indexes: 21 11
Complejidad de tiempo: O(N * logK), donde K es la ocurrencia máxima de cualquier carácter
Espacio auxiliar: O(d), d representa una array de tamaño 256 de unordered_set