Dado un texto txt[0..n-1] y un patrón pat[0..m-1] , escriba una función search(char pat[], char txt[]) que imprima todas las apariciones de pat[] en txt [] . Puede suponer que n > m.
Ejemplos:
Input: txt[] = "THIS IS A TEST TEXT"
pat[] = "TEST"
Output: Pattern found at index 10
Input: txt[] = "AABAACAADAABAABA"
pat[] = "AABA"
Output: Pattern found at index 0
Pattern found at index 9
Pattern found at index 12
La búsqueda de patrones es un problema importante en informática. Cuando buscamos una string en el bloc de notas/archivo de Word, en el navegador o en la base de datos, se utilizan algoritmos de búsqueda de patrones para mostrar los resultados de la búsqueda.
Hemos discutido los siguientes algoritmos en las publicaciones anteriores:
Algoritmo Naive Algoritmo
KMP Algoritmo
Rabin Karp
En esta publicación, discutiremos el algoritmo de búsqueda de patrones basado en Finite Automata (FA). En el algoritmo basado en FA, preprocesamos el patrón y construimos una array 2D que representa un autómata finito. La construcción de la FA es la principal parte complicada de este algoritmo. Una vez que se construye el FA, la búsqueda es simple. En la búsqueda, simplemente necesitamos comenzar desde el primer estado de los autómatas y el primer carácter del texto. En cada paso, consideramos el siguiente carácter del texto, buscamos el siguiente estado en el FA construido y pasamos a un nuevo estado. Si llegamos al estado final, entonces el patrón se encuentra en el texto. La complejidad temporal del proceso de búsqueda es O(n).
Antes de discutir la construcción de FA, echemos un vistazo a la siguiente FA para el patrón ACACAGA.
Los diagramas anteriores representan representaciones gráficas y tabulares del patrón ACACAGA.
El número de estados en FA será M+1 donde M es la longitud del patrón. Lo principal para construir FA es obtener el siguiente estado del estado actual para cada carácter posible. Dado un carácter x y un estado k, podemos obtener el siguiente estado considerando la string “pat[0..k-1]x” que es básicamente una concatenación de caracteres de patrón pat[0], pat[1] … pat[ k-1] y el carácter x. La idea es obtener la longitud del prefijo más largo del patrón dado, de modo que el prefijo también sea el sufijo de «pat[0..k-1]x». El valor de longitud nos da el siguiente estado. Por ejemplo, veamos cómo obtener el siguiente estado desde el estado actual 5 y el carácter ‘C’ en el diagrama anterior. Necesitamos considerar la string, “pat[0..4]C” que es “ACACAC”. La longitud del prefijo más largo del patrón tal que el prefijo es sufijo de “ACACAC” es 4 (“ACAC”).
En el siguiente código, computeTF() construye el FA. La complejidad de tiempo de computeTF() es O(m^3*NO_OF_CHARS) donde m es la longitud del patrón y NO_OF_CHARS es el tamaño del alfabeto (número total de caracteres posibles en el patrón y el texto). La implementación prueba todos los prefijos posibles comenzando por el más largo posible que puede ser un sufijo de “pat[0..k-1]x”. Hay mejores implementaciones para construir FA en O(m*NO_OF_CHARS) (Sugerencia: podemos usar algo como la construcción de arrays lps en el algoritmo KMP ). Hemos cubierto la mejor implementación en nuestra próxima publicación sobre la búsqueda de patrones .
C
// C program for Finite Automata Pattern searching
// Algorithm
#include<stdio.h>
#include<string.h>
#define NO_OF_CHARS 256
int getNextState(char *pat, int M, int state, int x)
{
// If the character c is same as next character
// in pattern,then simply increment state
if (state < M && x == pat[state])
return state+1;
// ns stores the result which is next state
int ns, i;
// ns finally contains the longest prefix
// which is also suffix in "pat[0..state-1]c"
// Start from the largest possible value
// and stop when you find a prefix which
// is also suffix
for (ns = state; ns > 0; ns--)
{
if (pat[ns-1] == x)
{
for (i = 0; i < ns-1; i++)
if (pat[i] != pat[state-ns+1+i])
break;
if (i == ns-1)
return ns;
}
}
return 0;
}
/* This function builds the TF table which represents4
Finite Automata for a given pattern */
void computeTF(char *pat, int M, int TF[][NO_OF_CHARS])
{
int state, x;
for (state = 0; state <= M; ++state)
for (x = 0; x < NO_OF_CHARS; ++x)
TF[state][x] = getNextState(pat, M, state, x);
}
/* Prints all occurrences of pat in txt */
void search(char *pat, char *txt)
{
int M = strlen(pat);
int N = strlen(txt);
int TF[M+1][NO_OF_CHARS];
computeTF(pat, M, TF);
// Process txt over FA.
int i, state=0;
for (i = 0; i < N; i++)
{
state = TF[state][txt[i]];
if (state == M)
printf ("\n Pattern found at index %d",
i-M+1);
}
}
// Driver program to test above function
int main()
{
char *txt = "AABAACAADAABAAABAA";
char *pat = "AABA";
search(pat, txt);
return 0;
}
CPP
// CPP program for Finite Automata Pattern searching
// Algorithm
#include <bits/stdc++.h>
using namespace std;
#define NO_OF_CHARS 256
int getNextState(string pat, int M, int state, int x)
{
// If the character c is same as next character
// in pattern,then simply increment state
if (state < M && x == pat[state])
return state+1;
// ns stores the result which is next state
int ns, i;
// ns finally contains the longest prefix
// which is also suffix in "pat[0..state-1]c"
// Start from the largest possible value
// and stop when you find a prefix which
// is also suffix
for (ns = state; ns > 0; ns--)
{
if (pat[ns-1] == x)
{
for (i = 0; i < ns-1; i++)
if (pat[i] != pat[state-ns+1+i])
break;
if (i == ns-1)
return ns;
}
}
return 0;
}
/* This function builds the TF table which represents4
Finite Automata for a given pattern */
void computeTF(string pat, int M, int TF[][NO_OF_CHARS])
{
int state, x;
for (state = 0; state <= M; ++state)
for (x = 0; x < NO_OF_CHARS; ++x)
TF[state][x] = getNextState(pat, M, state, x);
}
/* Prints all occurrences of pat in txt */
void search(string pat, string txt)
{
int M = pat.size();
int N = txt.size();
int TF[M+1][NO_OF_CHARS];
computeTF(pat, M, TF);
// Process txt over FA.
int i, state=0;
for (i = 0; i < N; i++)
{
state = TF[state][txt[i]];
if (state == M)
cout<<" Pattern found at index "<< i-M+1<<endl;
}
}
// Driver program to test above function
int main()
{
string txt = "AABAACAADAABAAABAA";
string pat = "AABA";
search(pat, txt);
return 0;
}
//This code is contributed by rathbhupendra
Java
// Java program for Finite Automata Pattern
// searching Algorithm
class GFG {
static int NO_OF_CHARS = 256;
static int getNextState(char[] pat, int M,
int state, int x)
{
// If the character c is same as next
// character in pattern,then simply
// increment state
if(state < M && x == pat[state])
return state + 1;
// ns stores the result which is next state
int ns, i;
// ns finally contains the longest prefix
// which is also suffix in "pat[0..state-1]c"
// Start from the largest possible value
// and stop when you find a prefix which
// is also suffix
for (ns = state; ns > 0; ns--)
{
if (pat[ns-1] == x)
{
for (i = 0; i < ns-1; i++)
if (pat[i] != pat[state-ns+1+i])
break;
if (i == ns-1)
return ns;
}
}
return 0;
}
/* This function builds the TF table which
represents Finite Automata for a given pattern */
static void computeTF(char[] pat, int M, int TF[][])
{
int state, x;
for (state = 0; state <= M; ++state)
for (x = 0; x < NO_OF_CHARS; ++x)
TF[state][x] = getNextState(pat, M, state, x);
}
/* Prints all occurrences of pat in txt */
static void search(char[] pat, char[] txt)
{
int M = pat.length;
int N = txt.length;
int[][] TF = new int[M+1][NO_OF_CHARS];
computeTF(pat, M, TF);
// Process txt over FA.
int i, state = 0;
for (i = 0; i < N; i++)
{
state = TF[state][txt[i]];
if (state == M)
System.out.println("Pattern found "
+ "at index " + (i-M+1));
}
}
// Driver code
public static void main(String[] args)
{
char[] pat = "AABAACAADAABAAABAA".toCharArray();
char[] txt = "AABA".toCharArray();
search(txt,pat);
}
}
// This code is contributed by debjitdbb.
Python3
# Python program for Finite Automata
# Pattern searching Algorithm
NO_OF_CHARS = 256
def getNextState(pat, M, state, x):
'''
calculate the next state
'''
# If the character c is same as next character
# in pattern, then simply increment state
if state < M and x == ord(pat[state]):
return state+1
i=0
# ns stores the result which is next state
# ns finally contains the longest prefix
# which is also suffix in "pat[0..state-1]c"
# Start from the largest possible value and
# stop when you find a prefix which is also suffix
for ns in range(state,0,-1):
if ord(pat[ns-1]) == x:
while(i<ns-1):
if pat[i] != pat[state-ns+1+i]:
break
i+=1
if i == ns-1:
return ns
return 0
def computeTF(pat, M):
'''
This function builds the TF table which
represents Finite Automata for a given pattern
'''
global NO_OF_CHARS
TF = [[0 for i in range(NO_OF_CHARS)]\
for _ in range(M+1)]
for state in range(M+1):
for x in range(NO_OF_CHARS):
z = getNextState(pat, M, state, x)
TF[state][x] = z
return TF
def search(pat, txt):
'''
Prints all occurrences of pat in txt
'''
global NO_OF_CHARS
M = len(pat)
N = len(txt)
TF = computeTF(pat, M)
# Process txt over FA.
state=0
for i in range(N):
state = TF[state][ord(txt[i])]
if state == M:
print("Pattern found at index: {}".\
format(i-M+1))
# Driver program to test above function
def main():
txt = "AABAACAADAABAAABAA"
pat = "AABA"
search(pat, txt)
if __name__ == '__main__':
main()
# This code is contributed by Atul Kumar
C#
// C# program for Finite Automata Pattern
// searching Algorithm
using System;
class GFG
{
public static int NO_OF_CHARS = 256;
public static int getNextState(char[] pat, int M,
int state, int x)
{
// If the character c is same as next
// character in pattern,then simply
// increment state
if (state < M && (char)x == pat[state])
{
return state + 1;
}
// ns stores the result
// which is next state
int ns, i;
// ns finally contains the longest
// prefix which is also suffix in
// "pat[0..state-1]c"
// Start from the largest possible
// value and stop when you find a
// prefix which is also suffix
for (ns = state; ns > 0; ns--)
{
if (pat[ns - 1] == (char)x)
{
for (i = 0; i < ns - 1; i++)
{
if (pat[i] != pat[state - ns + 1 + i])
{
break;
}
}
if (i == ns - 1)
{
return ns;
}
}
}
return 0;
}
/* This function builds the TF table which
represents Finite Automata for a given pattern */
public static void computeTF(char[] pat,
int M, int[][] TF)
{
int state, x;
for (state = 0; state <= M; ++state)
{
for (x = 0; x < NO_OF_CHARS; ++x)
{
TF[state][x] = getNextState(pat, M,
state, x);
}
}
}
/* Prints all occurrences of
pat in txt */
public static void search(char[] pat,
char[] txt)
{
int M = pat.Length;
int N = txt.Length;
int[][] TF = RectangularArrays.ReturnRectangularIntArray(M + 1,
NO_OF_CHARS);
computeTF(pat, M, TF);
// Process txt over FA.
int i, state = 0;
for (i = 0; i < N; i++)
{
state = TF[state][txt[i]];
if (state == M)
{
Console.WriteLine("Pattern found " +
"at index " + (i - M + 1));
}
}
}
public static class RectangularArrays
{
public static int[][] ReturnRectangularIntArray(int size1,
int size2)
{
int[][] newArray = new int[size1][];
for (int array1 = 0; array1 < size1; array1++)
{
newArray[array1] = new int[size2];
}
return newArray;
}
}
// Driver code
public static void Main(string[] args)
{
char[] pat = "AABAACAADAABAAABAA".ToCharArray();
char[] txt = "AABA".ToCharArray();
search(txt,pat);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript program for Finite Automata Pattern
// searching Algorithm
let NO_OF_CHARS = 256;
function getNextState(pat,M,state,x)
{
// If the character c is same as next
// character in pattern,then simply
// increment state
if(state < M && x == pat[state].charCodeAt(0))
return state + 1;
// ns stores the result which is next state
let ns, i;
// ns finally contains the longest prefix
// which is also suffix in "pat[0..state-1]c"
// Start from the largest possible value
// and stop when you find a prefix which
// is also suffix
for (ns = state; ns > 0; ns--)
{
if (pat[ns-1].charCodeAt(0) == x)
{
for (i = 0; i < ns-1; i++)
if (pat[i] != pat[state-ns+1+i])
break;
if (i == ns-1)
return ns;
}
}
return 0;
}
/* This function builds the TF table which
represents Finite Automata for a given pattern */
function computeTF(pat,M,TF)
{
let state, x;
for (state = 0; state <= M; ++state)
for (x = 0; x < NO_OF_CHARS; ++x)
TF[state][x] = getNextState(pat, M, state, x);
}
/* Prints all occurrences of pat in txt */
function search(pat,txt)
{
let M = pat.length;
let N = txt.length;
let TF = new Array(M+1);
for(let i=0;i<M+1;i++)
{
TF[i]=new Array(NO_OF_CHARS);
for(let j=0;j<NO_OF_CHARS;j++)
TF[i][j]=0;
}
computeTF(pat, M, TF);
// Process txt over FA.
let i, state = 0;
for (i = 0; i < N; i++)
{
state = TF[state][txt[i].charCodeAt(0)];
if (state == M)
document.write("Pattern found " + "at index " + (i-M+1)+"<br>");
}
}
// Driver code
let pat = "AABAACAADAABAAABAA".split("");
let txt = "AABA".split("");
search(txt,pat);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Pattern found at index 0 Pattern found at index 9 Pattern found at index 13
Complejidad del Tiempo: O(m 2 )
Espacio Auxiliar: O(m)
Referencias:
Introducción a los algoritmos por Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA