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 hacer 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 índice 1 y yen el índice 5) y diferentes caracteres 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 los índices 10 a 12 (en verde) no son un par máximo, ya que el carácter ysigue ambas subcadenas, por lo que pueden extenderse hacia la derecha para formar un par más largo.
Formalmente, un par máximo de subcadenas con posiciones iniciales y respectivamente, y ambas de longitud , se especifica mediante un triple , de modo que, dada una cadena de longitud , (lo que significa que las subcadenas tienen contenido idéntico), pero (tienen caracteres diferentes para su izquierda) y (también tienen diferentes caracteres a su derecha; juntas, estas dos desigualdades son la condición para ser máximas). Por lo tanto, en el ejemplo anterior, los pares máximos son (las subcadenas roja y azul) y (las subcadenas verde y azul), y no es un par máximo.
![{\ Displaystyle S [p_ {1} .. p_ {1} + l-1] = S [p_ {2} .. p_ {2} + l-1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b0f4761e93ae24b7cc3bafc64590289e814ce75)
![{\ Displaystyle S [p_ {1} -1] \ neq S [p_ {2} -1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b37107a03ee25d837c8d7292800a201de9eb69a4)
![{\ Displaystyle S [p_ {1} + l] \ neq S [p_ {2} + l]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f4b4852ff14d451f07786b92dfded60ec3933e73)
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 ocurre como una subcadena adecuada de otra repetición máxima. En el ejemplo anterior, abcy abcyson repeticiones máximas, pero solo abcyes una repetición supermáxima.