Sufijo en Cadena de Fibonacci


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Swift, VB

Son muy conocidos los números de Fibonacci y la forma en que se forman dichos números. El problema que se nos plantea ahora tiene mucho que ver con el anterior lo que ahora este se extiende hasta formar las cadenas de Fibonacci las cuales se definen de la siguiente manera:

Sean S_1 y S_2 dos caracteres (entre “a” y “z”).

La \(k-ésima\) cadena de Fibonacci (k > 2) se define como:

S_k = S_k-1 S_k-2 para k > 2 es decir concatenando las dos cadenas de Fibonacci anteriores.

Ejemplo:

S_1 = abc

S_2 = xyz

S_3 = S_2 S_1 = xyzabc

S_4 = S_3 S_2 = xyzabcxyz

….

Y así sucesivamente.

Se dice que una cadena x es sufijo de la cadena S si S termina con x.

Sean S y S_k cadenas de caracteres, se dice que S_k es sufijo de S, si para alguna cadena w se obtiene S = w S_k.

Nuestro problema consiste en dada una cadena S determine cuál es el mayor K tal que la cadena de Fibonacci S_k sea sufijo de la cadena S dada.

Tarea

Hacer un programa que permita:

• Leer desde la entrada estándar la cadena S y los dos caracteres iniciales de la secuencia de Fibonacci.

• Determinar el mayor valor de K tal que la cadena Fibonacci S_k sea sufijo de la cadena S.

• Escribir hacia la salida estándar el valor de K, o el dígito cero en caso de que no exista ningún S_k que sea sufijo de la cadena S dada.

Entrada

• Línea 1: El carácter S_1.

• Línea 2: El carácter S_2.

• Línea 3: N (1 \leq N \leq 10 000), cantidad de caracteres de la cadena S.

• Línea 4…N+3: En cada una de estas líneas se escribirá un carácter de la cadena S.

Salida

• Una sola línea en la que se escribirá el valor K.

Ejemplo de Entrada 1

a
b
8
s
a
g
b
a
b
b
a

Ejemplo de Salida 1

5

Ejemplo de Entrada 2

a
x
10
e
j
e
m
p
l
o
x
b
c

Ejemplo de Salida 2

0

Comments

There are no comments at the moment.