Saya menemukan masalah berikut di buku teks algoritma Ceko lama saya, sayangnya datang tanpa petunjuk atau solusi.
"Kami mendefinisikan kata-kata Fibonacci sebagai , F 1 = b , F n + 2 = F n F n + 1 , di mana a dan b adalah huruf umum. Bagaimana dalam string yang diberikan (lebih dari alfabet yang berpotensi besar) dapatkah Anda menemukan sub-kata Fibonacci terpanjang dalam waktu linier? "
Saya tahu solusi dalam waktu kuadratik, tetapi tidak dapat menguranginya menjadi linear. Adakah yang bisa mengarahkan saya ke arah yang benar?
Jawaban:
sumber