Requisitos previos:
El problema de la extensión común más larga (LCE) considera una string s y calcula, para cada par (L , R), la substring más larga de s que comienza tanto en L como en R. En LCE, en cada una de las consultas que tenemos que responder la longitud del prefijo común más largo que comienza en los índices L y R.
Ejemplo:
String : «abbababba»
Consultas: LCE (1, 2), LCE (1, 6) y LCE (0, 5)Encuentre la longitud del prefijo común más largo que comienza en el índice dado como (1, 2), (1, 6) y (0, 5) .
La string resaltada es el prefijo común más largo que comienza en el índice L y R de las consultas respectivas. Tenemos que encontrar la longitud del prefijo común más largo que comienza en index- (1, 2), (1, 6) y (0, 5) .
En el Conjunto 1 , explicamos el método ingenuo para encontrar la longitud del LCE de una string en muchas consultas. En este conjunto, mostraremos cómo un problema LCE puede reducirse a un problema RMQ, por lo tanto, disminuyendo la complejidad del tiempo asintótico del método ingenuo.
Reducción de LCE a RMQ
Deje que la string de entrada sea S y que las consultas tengan la forma LCE(L, R) . Deje que la array de sufijos para s sea Suff[] y la array lcp sea lcp[] .
La extensión común más larga entre dos sufijos SL y S R de S se puede obtener de la array lcp de la siguiente manera.
- Sea bajo el rango de S L entre los sufijos de S (es decir, Suff[bajo] = L).
- Sea alto el rango de S R entre los sufijos de S. Sin pérdida de generalidad, asumimos que bajo < alto.
- Entonces la extensión común más larga de S L y S R es lcp(bajo, alto) = min (bajo<=k< alto) lcp [k].
Prueba: Sea S L = S L …S L+C …s n y S R = S R …S R+c …s n , y sea c la extensión común más larga de S L y S R (es decir, S L … S L+C-1 = s norte …S R+c-1 ). Suponemos que la string S tiene un carácter centinela, de modo que ningún sufijo de S es un prefijo de ningún otro sufijo de S que no sea él mismo.
- Si bajo = alto – 1 entonces i = bajo y lcp[bajo] = c es la extensión común más larga de S L y S R y hemos terminado.
- Si bajo < alto -1, seleccione i tal lcp[i] es el valor mínimo en el intervalo [bajo, alto] de la array lcp. Entonces tenemos dos casos posibles:
- Si c < lcp[i] tenemos una contradicción porque S L . . . S L+lcp[i]-1 = S R . . . S R +lcp[i]-1 por la definición de la tabla LCP y el hecho de que las entradas de lcp corresponden a sufijos ordenados de S.
- si c > lcp[i], sea alto = Suff[i], de modo que S alto sea el sufijo asociado con la posición i. S i es tal que s alto . . . s alto+lcp[i]-1 = S L . . . S L+lcp[i]-1 y s alto . . . s alto+lcp[i]-1 = S R . . . S R+lcp[i]-1 , pero dado que S L . . . S L+c-1 = S R . . . S R+c-1 tenemos que la array lcp debería estar mal ordenada, lo cual es una contradicción.
Por lo tanto, tenemos c = lcp[i].
Por lo tanto, hemos reducido nuestra consulta de extensión común más larga a una consulta mínima de rango sobre un rango en lcp.
Algoritmo
- Para encontrar bajo y alto, primero debemos calcular la array de sufijos y luego, a partir de la array de sufijos, calculamos la array de sufijos inversa.
- También necesitamos la array lcp, por lo que usamos el algoritmo de Kasai para encontrar la array lcp a partir de la array de sufijos.
- Una vez que se hacen las cosas anteriores, simplemente encontramos el valor mínimo en la array lcp desde el índice, de menor a mayor (como se demostró anteriormente) para cada consulta.
El valor mínimo es la longitud del LCE para esa consulta.
Implementación
C++
// A C++ Program to find the length of longest common
// extension using Direct Minimum Algorithm
#include<bits/stdc++.h>
using namespace std;
// Structure to represent a query of form (L,R)
struct Query
{
int L, R;
};
// Structure to store information of a suffix
struct suffix
{
int index; // To store original index
int rank[2]; // To store ranks and next rank pair
};
// A utility function to get minimum of two numbers
int minVal(int x, int y) { return (x < y)? x: y; }
// A utility function to get minimum of two numbers
int maxVal(int x, int y) { return (x > y)? x: y; }
// A comparison function used by sort() to compare
// two suffixes Compares two pairs, returns 1 if
// first pair is smaller
int cmp(struct suffix a, struct suffix b)
{
return (a.rank[0] == b.rank[0])?
(a.rank[1] < b.rank[1]):
(a.rank[0] < b.rank[0]);
}
// This is the main function that takes a string 'txt'
// of size n as an argument, builds and return the
// suffix array for the given string
vector<int> buildSuffixArray(string txt, int n)
{
// A structure to store suffixes and their indexes
struct suffix suffixes[n];
// Store suffixes and their indexes in an array
// of structures.
// The structure is needed to sort the suffixes
// alphabetically and maintain their old indexes
// while sorting
for (int i = 0; i < n; i++)
{
suffixes[i].index = i;
suffixes[i].rank[0] = txt[i] - 'a';
suffixes[i].rank[1] =
((i+1) < n)? (txt[i + 1] - 'a'): -1;
}
// Sort the suffixes using the comparison function
// defined above.
sort(suffixes, suffixes+n, cmp);
// At his point, all suffixes are sorted according
// to first 2 characters. Let us sort suffixes
// according to first 4/ characters, then first 8
// and so on
// This array is needed to get the index in suffixes[]
// from original index. This mapping is needed to get
// next suffix.
int ind[n];
for (int k = 4; k < 2*n; k = k*2)
{
// Assigning rank and index values to first suffix
int rank = 0;
int prev_rank = suffixes[0].rank[0];
suffixes[0].rank[0] = rank;
ind[suffixes[0].index] = 0;
// Assigning rank to suffixes
for (int i = 1; i < n; i++)
{
// If first rank and next ranks are same as
// that of previous/ suffix in array, assign
// the same new rank to this suffix
if (suffixes[i].rank[0] == prev_rank &&
suffixes[i].rank[1] == suffixes[i-1].rank[1])
{
prev_rank = suffixes[i].rank[0];
suffixes[i].rank[0] = rank;
}
else // Otherwise increment rank and assign
{
prev_rank = suffixes[i].rank[0];
suffixes[i].rank[0] = ++rank;
}
ind[suffixes[i].index] = i;
}
// Assign next rank to every suffix
for (int i = 0; i < n; i++)
{
int nextindex = suffixes[i].index + k/2;
suffixes[i].rank[1] = (nextindex < n)?
suffixes[ind[nextindex]].rank[0]: -1;
}
// Sort the suffixes according to first k characters
sort(suffixes, suffixes+n, cmp);
}
// Store indexes of all sorted suffixes in the suffix array
vector<int>suffixArr;
for (int i = 0; i < n; i++)
suffixArr.push_back(suffixes[i].index);
// Return the suffix array
return suffixArr;
}
/* To construct and return LCP */
vector<int> kasai(string txt, vector<int> suffixArr,
vector<int> &invSuff)
{
int n = suffixArr.size();
// To store LCP array
vector<int> lcp(n, 0);
// Fill values in invSuff[]
for (int i=0; i < n; i++)
invSuff[suffixArr[i]] = i;
// Initialize length of previous LCP
int k = 0;
// Process all suffixes one by one starting from
// first suffix in txt[]
for (int i=0; i<n; i++)
{
/* If the current suffix is at n-1, then we don’t
have next substring to consider. So lcp is not
defined for this substring, we put zero. */
if (invSuff[i] == n-1)
{
k = 0;
continue;
}
/* j contains index of the next substring to
be considered to compare with the present
substring, i.e., next string in suffix array */
int j = suffixArr[invSuff[i]+1];
// Directly start matching from k'th index as
// at-least k-1 characters will match
while (i+k<n && j+k<n && txt[i+k]==txt[j+k])
k++;
lcp[invSuff[i]] = k; // lcp for the present suffix.
// Deleting the starting character from the string.
if (k>0)
k--;
}
// return the constructed lcp array
return lcp;
}
// A utility function to find longest common extension
// from index - L and index - R
int LCE(vector<int> lcp, vector<int>invSuff, int n,
int L, int R)
{
// Handle the corner case
if (L == R)
return (n-L);
int low = minVal(invSuff[L], invSuff[R]);
int high = maxVal(invSuff[L], invSuff[R]);
int length = lcp[low];
for (int i=low+1; i<high; i++)
{
if (lcp[i] < length)
length = lcp[i];
}
return (length);
}
// A function to answer queries of longest common extension
void LCEQueries(string str, int n, Query q[],
int m)
{
// Build a suffix array
vector<int>suffixArr = buildSuffixArray(str, str.length());
// An auxiliary array to store inverse of suffix array
// elements. For example if suffixArr[0] is 5, the
// invSuff[5] would store 0. This is used to get next
// suffix string from suffix array.
vector<int> invSuff(n, 0);
// Build a lcp vector
vector<int>lcp = kasai(str, suffixArr, invSuff);
for (int i=0; i<m; i++)
{
int L = q[i].L;
int R = q[i].R;
printf ("LCE (%d, %d) = %d\n", L, R,
LCE(lcp, invSuff, n, L, R));
}
return;
}
// Driver Program to test above functions
int main()
{
string str = "abbababba";
int n = str.length();
// LCA Queries to answer
Query q[] = {{1, 2}, {1, 6}, {0, 5}};
int m = sizeof(q)/sizeof(q[0]);
LCEQueries(str, n, q, m);
return (0);
}
LCE (1, 2) = 1 LCE (1, 6) = 3 LCE (0, 5) = 4
Análisis de Reducción al método RMQ
Tiempo Complejidad:
- Para construir el lcp y la array de sufijos se necesita un tiempo O(N.logN) .
- Para responder a cada consulta se necesita O(|invSuff[R] – invSuff[L]|) .
Por lo tanto, la complejidad temporal general es O(N.logN + Q. (|invSuff[R] – invSuff[L]|))
donde,
Q = Número de consultas LCE.
N = Longitud de la string de entrada.
invSuff[] = array de sufijos inversa de la string de entrada.
Aunque esto puede parecer un algoritmo ineficiente, este algoritmo generalmente supera a todos los demás algoritmos para responder a las consultas LCE.
Daremos una descripción detallada del rendimiento de este método en el siguiente conjunto.
Espacio auxiliar: Utilizamos el espacio auxiliar O(N) para almacenar arrays de sufijos lcp, sufijos y sufijos inversos.
Este artículo es una contribución de Rachit Belwariar . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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