Par máximo

En informática , un par máximo dentro de una cadena es un par de subcadenas coincidentes que son máximas, donde "máximo" significa que no es posible formar un par coincidente más largo extendiendo el rango de ambas subcadenas hacia la izquierda o hacia la derecha.

Por ejemplo, en esta tabla, las subcadenas en los índices 2 a 4 (en rojo) y los índices 6 a 8 (en azul) son un par máximo, porque contienen caracteres idénticos ( abc), y tienen caracteres diferentes a la izquierda ( xen el índice 1 y yen el índice 5) y caracteres diferentes a la derecha ( yen el índice 5 y wen el índice 9). De manera similar, las subcadenas en los índices 6 a 8 (en azul) y los índices 10 a 12 (en verde) son un par máximo.

Sin embargo, las subcadenas en los índices 2 a 4 (en rojo) y en los índices 10 a 12 (en verde) no forman un par máximo, ya que el carácter ysigue a ambas subcadenas, por lo que se pueden extender hacia la derecha para formar un par más largo.

Formalmente, un par máximo de subcadenas con posiciones iniciales${\displaystyle p_{1}}$y${\displaystyle p_{2}}$respectivamente, y ambos de longitud${\displaystyle l}$, se especifica mediante una tripleta${\displaystyle (p_{1},p_{2},l)}$, de tal manera que, dada una cadena${\displaystyle S}$de longitud${\displaystyle n}$,${\displaystyle S[p_{1}..p_{1}+l-1]=S[p_{2}..p_{2}+l-1]}$(lo que significa que las subcadenas tienen contenido idéntico), pero${\displaystyle S[p_{1}-1]\neq S[p_{2}-1]}$(tienen caracteres diferentes a su izquierda) y${\displaystyle S[p_{1}+l]\neq S[p_{2}+l]}$(también tienen caracteres diferentes a su derecha; juntas, estas dos desigualdades son la condición para ser maximales). Por lo tanto, en el ejemplo anterior, los pares maximales son${\displaystyle (2,6,3)}$(las subcadenas roja y azul) y${\displaystyle (6,10,3)}$(las subcadenas verde y azul), y${\displaystyle (2,10,3)}$no es un par máximo.

Una repetición máxima es la cadena representada por un par máximo. Una repetición supermáxima es una repetición máxima que nunca aparece como subcadena propia de otra repetición máxima. En el ejemplo anterior, abcy abcyson ambas repeticiones máximas, pero solo abcyes una repetición supermáxima.

Los pares máximos, las repeticiones máximas y las repeticiones supermáximas se pueden encontrar en${\displaystyle \Theta (n+z)}$tiempo usando un árbol de sufijos , ^{[ 1 ]} si hay${\displaystyle z}$tales estructuras.

• Proyecto para el cálculo de todas las repeticiones máximas en una o más cadenas en Python , utilizando un array de sufijos .