Función de prefijo

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 12 de abril de 2022; las comprobaciones requieren 4 ediciones .

La función de prefijo de una cadena y una posición en ella es la longitud del prefijo propio más grande (no igual a toda la subcadena) de la subcadena , que también es el sufijo de esta subcadena. $S$ $i$ $k$ ${\ estilo de visualización S [1..i]}$

Es decir, al comienzo de una subcadena de longitud , debe encontrar un prefijo de la longitud máxima que sería el sufijo de esta subcadena . ${\ estilo de visualización S [1..i]}$ $i$ ${\ estilo de visualización k <i}$ $\left(S[1..k]=S\left[(i-k+1)..i\right]\right)$

denotado ; donde es una cadena; es la longitud de la subcadena en S. Se supone que . ${\ estilo de visualización \ pi (S, i)}$ ${\ estilo de visualización S \ en \ Sigma ^ {+))$ $1\leqslant i\leqslant \left|S\right|$ ${\ estilo de visualización \ pi (S, 1) = 0}$

A menudo, la función de prefijo se define en forma de vector:

La función de prefijo de una cadena es un vector , cada elemento del cual es igual a . ${\ estilo de visualización S \ en \ Sigma ^ {+))$ ${\displaystyle \pi (S)\in \mathbb {Z} ^{\left|S\right|))$ $i$ ${\ estilo de visualización \ pi (S, i)}$

Por ejemplo, para una cadena, la función de prefijo sería: . ${\texttt {abcdabscabcdabia))$ $\pi ({\texttt {abcdabscabcdabia)))=[0,0,0,0,1,2,0,0,1,2,3,4,5,6,0,1]$

Esta función se utiliza, por ejemplo, en el algoritmo Knuth-Morris-Pratt .

Algoritmo de cálculo

Buscar sílabas repetidas no en una palabra, sino en un texto, ¿una línea a partir de los primeros caracteres? Los caracteres de línea se numeran a partir del 1.

deja _ Intentemos calcular la función de prefijo para . ${\ estilo de visualización \ pi (S, i) = k}$ $yo+1$

Si , entonces, por supuesto, . Si no, pruebe con sufijos más pequeños. No es necesario iterar sobre todos los sufijos con una búsqueda lineal. Puede utilizar los valores ya calculados de la función de prefijo. Puede ver que también será el sufijo de la cadena , ya que es la longitud máxima del prefijo-sufijo en este punto. Para cualquier cadena, no habrá sufijo. Así, el algoritmo resulta: ${\ estilo de visualización S[i+1]=S[k+1]}$ ${\ estilo de visualización \ pi (S, i + 1) = k + 1}$ ${\ estilo de visualización S [1 \ ldots \ pi (S, k)]}$ $S[1\ldots i]$ $k$ ${\ estilo de visualización j \ en (k, i)}$ $S[1\ldots j]$

Cuando - poner . ${\ estilo de visualización S[i+1]=S[k+1]}$ ${\ estilo de visualización \ pi (S, i + 1) = k + 1}$
De lo contrario, cuando - poner . $k=0$ ${\ estilo de visualización \ pi (S, i + 1) = 0}$
De lo contrario, instale y vaya al paso 1. ${\ estilo de visualización k: = \ pi (S, k)}$

Para una cadena , el 'abcdabcabcdabcdab'cálculo sería:

1 S[1]='a', k=π=0; 2 S[2]='b'!=S[k+1] => k=π=0; 3 S[3]='c'!=S[1] => k=π=0; 4 S[4]='d'!=S[1] => k=π=0; 5 S[5]='a'==S[1] => k=π=1; 6 S[6]='b'==S[2] => k=π=2; 7 S[7]='c'==S[3] => k=π=3; 8 S[8]='a'!=S[4] => k:=π(S, 3)=0, S[8]==S[1] => k=π=1; 9 S[9]='b'==S[2] => k=π=2; 10 S[10]='c'==S[3] => k=π=3; 11 S[11]='d'==S[4] => k=π=4; 12 S[12]='a'==S[5] => k=π=5; 13 S[13]='b'==S[6] => k=π=6; 14 S[14]='c'==S[7] => k=π=7; 15 S[15]='d'!=S[8] => k:=π(S, 7)=3, S[15]==S[4] => k=π=4; 16 S[16]='a'==S[5] => k=π=5; 17 S[17]='b'==S[6] => k=π=6;

Y el resultado es: [0,0,0,0,1,2,3,1,2,3,4,5,6,7,4,5,6].

Velocidad de trabajo

A pesar de que el elemento 3 es un ciclo interno, el tiempo de cálculo de la función de prefijo se estima como . Demostrémoslo. ${\ estilo de visualización O (| S |)}$

Todos se dividen en: $i$

incrementando en uno. El bucle pasa por una iteración. $k$
Sin cambiar el cero . El bucle también pasa por una iteración. Casos 1 y 2 en total no más de piezas. $k$ ${\ estilo de visualización \ izquierda | S \ derecha | -1}$
No cambies ni reduzcas lo positivo . Dado que el valor solo puede disminuir dentro del ciclo, y el aumento solo es posible en uno, el valor total no puede disminuir más de una vez, lo que limita la cantidad de veces que se ejecuta el ciclo interno. $k$ $k$ $k$ $k$ ${\ estilo de visualización \ izquierda | S \ derecha | -2}$

En total, el algoritmo no requiere más que iteraciones, lo que demuestra el orden de la velocidad . Lo “peor” para el algoritmo es el caso de procesar una cadena de la forma . ${\ estilo de visualización 2 \ izquierda | S \ derecha |}$ $O(\izquierda|S\derecha|)$ 'aa…ab'

Ejemplo de implementación en Python

prefijo def ( s ): p = [ 0 ] * len ( s ) for i in range ( 1 , len ( s )): k = p [ i - 1 ] while k > 0 y s [ k ] != s [ i ]: k = p [ k - 1 ] si s [ k ] == s [ i ]: k += 1 p [ i ] = k return p

Enlaces

Búsqueda de subcadenas y preguntas relacionadas Archivado el 15 de enero de 2016 en Wayback Machine - Artículo de Habr

Instrumentos de cuerda
Medidas de similitud de cadenas	Distancia de Damerau a Loewenstein distancia Levenstein distancia de hamming Similitudes Jaro-Winkler
Búsqueda de subcadena	Algoritmo de Boyer-Moore Algoritmo de Boyer-Moore-Horspool Algoritmo de Knuth-Morris-Pratt Algoritmo de Rabin-Karp función de prefijo Función Z Algoritmo Aho - Korasik
palíndromos	árbol palíndromo Algoritmo del administrador
Alineación de secuencia	Algoritmo de Needleman-Wunsha Algoritmo de Smith-Waterman
Estructuras de sufijos	Matriz de sufijos sufijo autómata árbol de sufijos árbol de prefijos
Otro	analizando La coincidencia de patrones Mayor subsecuencia común Mayor subcadena común