Función Z
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 4 de agosto de 2021; la verificación requiere 1 edición .La función z de una cadena es una matriz tal que es igual a la longitud del prefijo común más largo que comienza en la posición del sufijo de la cadena y la cadena misma . El algoritmo de construcción fue descrito por Dan Gasfield en su libro Strings, Trees and Sequences in Algorithms. Computer Science and Computational Biology” en 1997 [1] basado en el artículo de Maine y Lorenz de 1984 [2] sobre la búsqueda de todas las repeticiones en tándem en una cadena.
La función Z se utiliza en varios algoritmos de procesamiento de cadenas. En particular, puede usarse para resolver rápidamente el problema de encontrar una ocurrencia de una cadena en otra ( búsqueda por patrón ).
Algoritmo de cálculo
Los caracteres de línea se numeran desde 0.Almacenaremos los índices L y R , que denotan el principio y el final del prefijo con el mayor valor de R encontrado hasta el momento . inicialmente _
Conozcamos los valores de la función Z para las posiciones 1… i − 1. Tratemos de calcular el valor de la función Z para la posición i . Si , considere el valor de la función Z para la posición . If , entonces , ya que estamos en una subcadena que coincide con el prefijo de toda la cadena. Si , entonces es necesario calcular el valor de Z [ i ] mediante un bucle simple que recorre los caracteres después de R hasta que haya un carácter que no coincida con el carácter correspondiente del prefijo. Después de eso, cambiamos el valor de L a i y el valor de R al número del último carácter que coincide con el carácter correspondiente del prefijo.
![yo \en [L..R]](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fe0f4210173b6b36cf50743eb42ef04136f6b2d)
![i + Z[j] \leqslant R](https://wikimedia.org/api/rest_v1/media/math/render/svg/83b84625c3595c8646681ed1dc8221bb962b12da)
![Z[i] = Z[j]](https://wikimedia.org/api/rest_v1/media/math/render/svg/f870c16cc4149c1355767b45cd2e71b80484f211)
![yo + Z[j] > R](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cf0ccebb8ddeca7d44d7b978fad0b6ed3eac6be)
Si , entonces consideramos el valor de Z [ i ] como un bucle simple que compara los caracteres de la subcadena que comienza con el i -ésimo carácter y los caracteres correspondientes del prefijo. Cuando se encuentra una discrepancia o se llega al final de la línea, cambie el valor de L por i y el valor de R por el número del último carácter que coincida con el carácter correspondiente del prefijo.
![yo \ notin [L..R]](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7bc389ea5d3117fde5679222adc74f9a2262385)
Velocidad de trabajo
El tiempo de ejecución del algoritmo que calcula el valor de la función Z de la cadena S se estima en . Demostrémoslo.
Considere el i -ésimo carácter de la cadena. En el algoritmo, se considera no más de dos veces: la primera vez cuando cae en el segmento y la segunda vez cuando se calcula Z [ i ].
Por lo tanto, el bucle no procesa más que iteraciones.
Ejemplos de uso
1) La función Z se puede usar para buscar un patrón T en una cadena S ,
2) Conociendo la función Z de una cadena, se puede restaurar de forma única la función de prefijo de esta cadena, y viceversa.
Ejemplo de implementación en Python
def z_func ( s ): z = [ 0 ] * largo ( s ) izquierda , derecha = 0 , 0 para i en rango ( 1 , len ( s )): z [ i ] = max ( 0 , min ( z [ i - izquierda ], derecha - i )) mientras que i + z [ i ] < len ( s ) y s [ z [ i ]] == s [ i + z [ i ]]: z [ yo ] += 1 si i + z [ i ] > derecha : izquierda , derecha = yo , yo + z [ yo ] volver zVéase también
Notas
- ↑ Gusfield D. Algorithms on Strings, Trees, and Sequences (ing.) : Informática y biología computacional - Cambridge University Press , 1997. - 556 p. - ISBN 978-0-511-57493-1 - doi:10.1017/CBO9780511574931
- ↑ Main M. G., Lorentz R. J. Un algoritmo O(n log n) para encontrar todas las repeticiones en una cadena // Journal of Algorithms - Academic Press , 1984. - Vol. 5, edición. 3.- Pág. 422-432. — ISSN 0196-6774 ; 1090-2678 - doi:10.1016/0196-6774(84)90021-X
Enlaces
- Artículo sobre MAXimal::algo
- Tarea a comprobar (enlace no disponible)
| Instrumentos de cuerda | |
|---|---|
| Medidas de similitud de cadenas | |
| Búsqueda de subcadena | |
| palíndromos | |
| Alineación de secuencia | |
| Estructuras de sufijos | |
| Otro | |