Para resolver este problema, la enumeración habitual no funcionará, porque sus asintóticas serán O(t*s). Por lo tanto, para las tareas de búsqueda de subcadenas, se utiliza el algoritmo KMP (Knuth-Morris-Pratt).
Para implementar este algoritmo se utiliza la función de prefijo de cadena, esta es una matriz de números de longitud n (strong>s longitud), en la que cada elemento es la longitud máxima del mayor sufijo propio de la subcadena s, coincidiendo con su prefijo. Por ejemplo:
| Línea |
Función de prefijo |
Nota |
| abababcab |
0 0 1 2 3 4 0 1 2 |
|
| abcabcd |
0 0 0 1 2 3 0 |
|
| aabaaab |
0 1 0 1 2 2 3 |
|
Algoritmo de función de prefijo trivial con asintóticas O(n^3):
vector<int> función_prefijo (cadena s) {
int n = (int ) s.longitud();
vector<int>pi(n);
para (int i=0; i<n; ++i)
para (int k=0; k<=i; ++k)
si (s.substr(0,k) == s .substr(i-k+1,k))
pi[i] = k;
regresarpi;
}
Y ahora necesitamos hacer una función de prefijo para una cadena de la forma: & nbsp; t + # + s, donde # es un carácter delimitador que claramente no está en el texto. Al analizar los valores de la función de prefijo después del carácter separador correspondiente, se debe tener en cuenta que si el valor resultante es igual a la longitud de la subcadena deseada, entonces se encuentra su aparición. Por ejemplo, para la cadena "abababcab" y la subcadena deseada "abab", la función de prefijo será:
0 0 1 2 0 1 2 3 4 3 4 0 1 2 necesitamos analizar los elementos de la cadena correspondiente s:
1 2 3 4 3 4 0 1 2 - hay dos casos en los que el valor es 4 (4º y 6º), es decir longitud t, como resultado, la respuesta debe escribirse: 4 - 4 (longitud t) & nbsp; = 0 y 6 - 4 = 2. Se puede ver que estas son las respuestas correctas y la cadena "abab" es en realidad una subcadena en la cadena "abababcab" en las posiciones 0 y 2.
|
Después de optimizar la función de prefijo (para detalles aquí ), obtenemos el algoritmo final con asintóticas O(n):
vector<int> función_prefijo (cadena s) {
int n = (int ) s.longitud();
vector<int>pi(n);
para (int i=1; i<n; ++i) {
int j = pi[i-1< /intervalo>];
mientras (j > 0 && s[i] != s[j])
j = pi[j-1];
si (s[i] == s[j]) ++j;
pi[i] = j;
}
regresarpi;
}
|
Z-función
Z-función de la cadena S - matriz Z, cada elemento del cual es Z [i ] es igual al prefijo más largo de la subcadena que comienza en la posición i en la cadena S, que también es el prefijo de la cadena completa Z. El valor de la función Z en la posición cero suele ser cero o la longitud de la cadena completa.
Dificultad
O(|S| ^ 2) o O(|S|).
Función de prefijo de la cadena S - matriz P, cada elemento del cual P[i] es igual al sufijo más largo del subcadena que comienza desde la posición i en la cadena S, que también es el sufijo de la cadena completa S. El valor de la función P en la posición cero suele ser cero o la longitud de la cadena completa.
Dificultad
O(|S| ^ 2) o O(|S|).
Intente implementar función Z y función de prefijo para O(|S| ^ 2) .
|
Tanto Z como el prefijo de función se pueden usar para implementar el algoritmo KMP(Knuth-Morris-Pratt) para encontrar una subcadena en una cadena en O(|S|). La esencia de este algoritmo es la siguiente: atribuimos a la cadena que queremos encontrar la cadena en la que estamos buscando. Es muy recomendable poner un carácter separador entre estas líneas, es decir, un carácter que no aparece en ninguna línea (generalmente #).
|