En la publicación anterior , discutimos el algoritmo de búsqueda de patrones basado en Finite Automata. El método de construcción FA (Finite Automata) discutido en la publicación anterior toma O ((m ^ 3) * NO_OF_CHARS) tiempo. FA se puede construir en tiempo O(m*NO_OF_CHARS). En esta publicación, discutiremos el algoritmo O(m*NO_OF_CHARS) para la construcción de FA. La idea es similar a la construcción de arrays LP (sufijo de prefijo más largo) discutida en el algoritmo KMP . Usamos filas previamente llenas para llenar una nueva fila.
Los diagramas anteriores representan representaciones gráficas y tabulares del patrón ACACAGA.
Algoritmo:
1) Rellene la primera fila. Todas las entradas de la primera fila son siempre 0 excepto la entrada del carácter pat[0]. Para el carácter pat[0], siempre necesitamos ir al estado 1.
2) Inicialice lps como 0. lps para el primer índice siempre es 0.
3) Haga lo siguiente para las filas en el índice i = 1 a M. (M es el longitud del patrón)
…..a) Copie las entradas de la fila en el índice igual a lps.
…..b) Actualice la entrada para el carácter pat[i] a i+1.
…..c) Actualizar lps “lps = TF[lps][pat[i]]” donde TF es la array 2D que se está construyendo.
A continuación se muestra la implementación del algoritmo anterior.
Implementación
C++
#include <bits/stdc++.h>
using namespace std;
#define NO_OF_CHARS 256
/* This function builds the TF table
which represents Finite Automata for a
given pattern */
void computeTransFun(char* pat, int M, int TF[][NO_OF_CHARS])
{
int i, lps = 0, x;
// Fill entries in first row
for (x = 0; x < NO_OF_CHARS; x++)
TF[0][x] = 0;
TF[0][pat[0]] = 1;
// Fill entries in other rows
for (i = 1; i <= M; i++) {
// Copy values from row at index lps
for (x = 0; x < NO_OF_CHARS; x++)
TF[i][x] = TF[lps][x];
// Update the entry corresponding to this character
TF[i][pat[i]] = i + 1;
// Update lps for next row to be filled
if (i < M)
lps = TF[lps][pat[i]];
}
}
/* 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];
computeTransFun(pat, M, TF);
// process text over FA.
int i, j = 0;
for (i = 0; i < N; i++) {
j = TF[j][txt[i]];
if (j == M) {
cout << "pattern found at index " << i - M + 1 << endl;
}
}
}
/* Driver code */
int main()
{
char txt[] = "ACACACACAGAAGA ACACAGAACACAGA GEEKS";
char pat[] = "ACACAGA";
search(pat, txt);
return 0;
}
// This is code is contributed by rathbhupendra
Java
/* A Java program to answer queries to check whether
the substrings are palindrome or not efficiently */
class GFG
{
static int NO_OF_CHARS = 256;
/* This function builds the TF table
which represents Finite Automata for a
given pattern */
static void computeTransFun(char[] pat,
int M, int TF[][])
{
int i, lps = 0, x;
// Fill entries in first row
for (x = 0; x < NO_OF_CHARS; x++)
{
TF[0][x] = 0;
}
TF[0][pat[0]] = 1;
// Fill entries in other rows
for (i = 1; i < M; i++)
{
// Copy values from row at index lps
for (x = 0; x < NO_OF_CHARS; x++)
{
TF[i][x] = TF[lps][x];
}
// Update the entry corresponding to this character
TF[i][pat[i]] = i + 1;
// Update lps for next row to be filled
if (i < M)
{
lps = TF[lps][pat[i]];
}
}
}
/* 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];
computeTransFun(pat, M, TF);
// process text over FA.
int i, j = 0;
for (i = 0; i < N; i++)
{
j = TF[j][txt[i]];
if (j == M)
{
System.out.println("pattern found at index " +
(i - M + 1));
}
}
}
/* Driver code */
public static void main(String[] args)
{
char txt[] = "GEEKS FOR GEEKS".toCharArray();
char pat[] = "GEEKS".toCharArray();
search(pat, txt);
}
}
// This code is contributed by Princi Singh
Python3
""" A Python3 program to answer queries to check whether
the substrings are palindrome or not efficiently """
NO_OF_CHARS = 256
""" This function builds the TF table
which represents Finite Automata for a
given pattern """
def computeTransFun(pat, M, TF):
lps = 0
# Fill entries in first row
for x in range(NO_OF_CHARS):
TF[0][x] = 0
TF[0][ord(pat[0])] = 1
# Fill entries in other rows
for i in range(1, M+1):
# Copy values from row at index lps
for x in range(NO_OF_CHARS):
TF[i][x] = TF[lps][x]
if (i < M):
# Update the entry corresponding to this character
TF[i][ord(pat[i])] = i + 1
# Update lps for next row to be filled
lps = TF[lps][ord(pat[i])]
# Prints all occurrences of pat in txt
def search(pat, txt):
M = len(pat)
N = len(txt)
TF = [[0 for i in range(NO_OF_CHARS)] for j in range(M + 1)]
computeTransFun(pat, M, TF)
# process text over FA.
j = 0
for i in range(N):
j = TF[j][ord(txt[i])]
if (j == M):
print("pattern found at index", i - M + 1)
# Driver code
txt = "ACACACACAGAAGA ACACAGAACACAGA GEEKS"
pat = "ACACAGA"
search(pat, txt)
# This code is contributed by divyeshrabadiya07
C#
/* A C# program to answer queries to check whether
the substrings are palindrome or not efficiently */
using System;
class GFG
{
static int NO_OF_CHARS = 256;
/* This function builds the TF table
which represents Finite Automata for a
given pattern */
static void computeTransFun(char[] pat,
int M, int [,]TF)
{
int i, lps = 0, x;
// Fill entries in first row
for (x = 0; x < NO_OF_CHARS; x++)
{
TF[0,x] = 0;
}
TF[0,pat[0]] = 1;
// Fill entries in other rows
for (i = 1; i < M; i++)
{
// Copy values from row at index lps
for (x = 0; x < NO_OF_CHARS; x++)
{
TF[i,x] = TF[lps,x];
}
// Update the entry corresponding to this character
TF[i,pat[i]] = i + 1;
// Update lps for next row to be filled
if (i < M)
{
lps = TF[lps,pat[i]];
}
}
}
/* 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];
computeTransFun(pat, M, TF);
// process text over FA.
int i, j = 0;
for (i = 0; i < N; i++)
{
j = TF[j,txt[i]];
if (j == M)
{
Console.WriteLine("pattern found at index " +
(i - M + 1));
}
}
}
/* Driver code */
public static void Main(String[] args)
{
char []txt = "GEEKS FOR GEEKS".ToCharArray();
char []pat = "GEEKS".ToCharArray();
search(pat, txt);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
/* A Javascript program to answer queries to check whether
the substrings are palindrome or not efficiently */
let NO_OF_CHARS = 256;
/* This function builds the TF table
which represents Finite Automata for a
given pattern */
function computeTransFun(pat,M,TF)
{
let i, lps = 0, x;
// Fill entries in first row
for (x = 0; x < NO_OF_CHARS; x++)
{
TF[0][x] = 0;
}
TF[0][pat[0].charCodeAt(0)] = 1;
// Fill entries in other rows
for (i = 1; i < M; i++)
{
// Copy values from row at index lps
for (x = 0; x < NO_OF_CHARS; x++)
{
TF[i][x] = TF[lps][x];
}
// Update the entry corresponding to this character
TF[i][pat[i].charCodeAt(0)] = i + 1;
// Update lps for next row to be filled
if (i < M)
{
lps = TF[lps][pat[i].charCodeAt(0)];
}
}
}
/* 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;
}
}
computeTransFun(pat, M, TF);
// process text over FA.
let i, j = 0;
for (i = 0; i < N; i++)
{
j = TF[j][txt[i].charCodeAt(0)];
if (j == M)
{
document.write("pattern found at index " +
(i - M + 1)+"<br>");
}
}
}
/* Driver code */
let txt = "GEEKS FOR GEEKS".split("");
let pat = "GEEKS".split("");
search(pat, txt);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
pattern found at index 0 pattern found at index 10
La complejidad de tiempo para la construcción de FA es O(M*NO_OF_CHARS). El código de búsqueda es el mismo que el de la publicación anterior y la complejidad de tiempo es O(n).
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