Sufijo en Cadena de Fibonacci
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 y dos caracteres (entre “a” y “z”).
La \(k-ésima\) cadena de Fibonacci se define como:
para es decir concatenando las dos cadenas de Fibonacci anteriores.
Ejemplo:
abc
xyz
xyzabc
xyzabcxyz
….
Y así sucesivamente.
Se dice que una cadena es sufijo de la cadena si termina con .
Sean y cadenas de caracteres, se dice que es sufijo de , si para alguna cadena se obtiene .
Nuestro problema consiste en dada una cadena determine cuál es el mayor tal que la cadena de Fibonacci sea sufijo de la cadena dada.
Tarea
Hacer un programa que permita:
• Leer desde la entrada estándar la cadena y los dos caracteres iniciales de la secuencia de Fibonacci.
• Determinar el mayor valor de tal que la cadena Fibonacci sea sufijo de la cadena .
• Escribir hacia la salida estándar el valor de , o el dígito cero en caso de que no exista ningún que sea sufijo de la cadena dada.
Entrada
• Línea 1: El carácter .
• Línea 2: El carácter .
• Línea 3: , cantidad de caracteres de la cadena .
• Línea 4…N+3: En cada una de estas líneas se escribirá un carácter de la cadena .
Salida
• Una sola línea en la que se escribirá el valor .
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