0x43 - Encontrar el borde más largo de una string

Un borde de una string S es otra string más corta que S que aparece al principio y al final de S. En otras palabras, B es un borde de S si S empieza por B y también S termina en B.

Por ejemplo, la string xyz es un borde de la string xyzcodeoxyz porque xyzcodeoxyz empieza por xyz y también termina en xyz:

La string xy no es un borde de xyzcodeoxyz porque aunque xyzcodeoxyz empieza por xy, no termina en xy:

(Similarmente, la string yz no es un borde de xyzcodeoxyz porque aunque aunque aparece al final, no aparece al principio.)

A veces, una string puede tener más de un borde. Por ejemplo, tanto a como aba son bordes de abacaba:

Escribe un programa que lee una string S y calcula la longitud del borde más largo de S.

Aclaraciones

• Es posible que ambos "lados" del borde se sobrepongan y compartan caracteres en el medio. Esto es un caso válido y debe ser considerado. Por ejemplo, el borde más largo de la string abacabacaba es abacaba porque aparece al principio y al final (y no importa que ambas occurrencias compartan caracteres en el medio):

• Por definición, un borde de S tiene que ser más corto que S: si S tiene longitud N, entonces la longitud de cualquier borde de S puede ser máximo N-1 (de lo contrario el borde más largo siempre sería S, porque una string siempre empieza y termina por ella misma).

• Es posible que una string no tenga ningún borde. Por ejemplo, la string xyz no tiene ningún borde. En este caso la respuesta es 0. (Otra manera de pensarlo sería decir que la string vacía siempre aparece al principio y al final de cualquier otra string, entonces una string de longitud 0 siempre es un borde válido).

Entrada

La entrada tiene una única línea con una string S. La string sólo tiene letras minúsculas entre a y z. No hay tildes, diéresis, espacios, eñes, números o signos de puntuación.

Restricciones

• En aproximadamente 30% de los casos, 1 ≤ |S| ≤ 500.
• En el resto de los casos, 1 ≤ |S| ≤ 100,000.

Salida

La salida debe tener exactamente una línea con un entero: la longitud del borde más largo de S.

Si S no tiene ningún borde no vacío, la salida debe ser 0.

Entrada de ejemplo #1

xyzcodeoxyz

Salida de ejemplo #1

3

Explicación del ejemplo #1

El único borde no vacío de xyzcodeoxyz es xyz y tiene longitud 3.

Entrada de ejemplo #2

abacaba

Salida de ejemplo #2

3

Explicación del ejemplo #2

abacaba tiene 2 bordes no vacíos: a y aba. El más largo tiene longitud 3.

Entrada de ejemplo #3

abacabacaba

Salida de ejemplo #3

7

Explicación del ejemplo #3

abacaba tiene longitud 7 y es un borde de abacabacaba. No es el único; a y aba también son bordes válidos pero son más cortos.

Entrada de ejemplo #4

aaaa

Salida de ejemplo #4

3

Explicación del ejemplo #4

Si una string tiene N caracteres iguales, la respuesta siempre es N-1.

Entrada de ejemplo #5

xyz

Salida de ejemplo #5

0

Explicación del ejemplo #5

xyz no tiene ningún borde no vacío, entonces la respuesta es 0.

Envía tu solución