Kata-kata Fibonacci

11

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? "F0=aF1=bFn+2=FnFn+1ab

Saya tahu solusi dalam waktu kuadratik, tetapi tidak dapat menguranginya menjadi linear. Adakah yang bisa mengarahkan saya ke arah yang benar?

Fanda
sumber
3
Apa nama dari buku teks algoritma Ceko yang lama ini ;-)
Saeed
Apakah sub-kata harus bersebelahan (yaitu faktor) dalam buku ini?
Klaus Draeger

Jawaban:

12

F(i,j)ijF(i2,j)F(i1,j+fib(i))O(nlogn)i.

O(n/fib(i))F(i2,j)F(i2,j)F(i,j)O(n)ii2i

FO(nlogn)FO(n) logn

David Eppstein
sumber
Bisakah Anda ceritakan, mengapa Anda berpikir bahwa pemrograman dinamis akan menjadi pilihan terbaik untuk masalah ini? Di mana kita akan menghadapi masalah jika kita menggunakan pemrograman statis seperti C ?
tarit goswami
1
Pemrograman dinamis adalah teknik desain algoritma, bukan kelas bahasa pemrograman.
David Eppstein