Слова Фибоначчи

11

В моем старом учебнике по чешскому алгоритму я столкнулся со следующей проблемой, к сожалению, без подсказок и решений.

«Мы определяем слова Фибоначчи как , , , где и - общие буквы. Как в данном строка (над потенциально большим алфавитом) вы можете найти самое длинное подслово Фибоначчи за линейное время? "F 1 = b F n + 2 = F n F n + 1 a bF0знак равноaF1знак равнобFN+2знак равноFNFN+1aб

Я знаю решение в квадратичном времени, но не могу свести его к линейному. Кто-нибудь может указать мне правильное направление?

Fanda
источник
3
Как называется этот старый учебник по чешскому алгоритму ;-)
Саид
Должны ли подслови быть смежными (то есть факторами) в этой книге?
Клаус Дрегер

Ответы:

12

Очевидный путь - динамическое программирование: пусть хранит две буквы, для которых слово порядка Фибоначчи i начинается с позиции j , и вычисляет это, рассматривая F ( i - 2 , j ) и F ( i - 1 , j + fib ( i ) ) . Это занимает не более O ( n log n ) времени, поскольку существует только логарифмически много возможных значений iF(я,J)яJF(я-2,J)F(я-1,J+выдумка(я))О(NжурналN)я,

Но я подозреваю, что могут быть только позиции для которых F ( i - 2 , j ) непуста (то есть, что при наличии двух слов Фибоначчи одинаковой длины они могут перекрываться только до постоянная доля их длины, а не большая часть их длины). Непустые позиции F ( i - 2 , j ) - единственные, для которых вам нужно вычислить (постоянное время) для F ( i , j )О(N/выдумка(я))F(я-2,J)F(я-2,J)F(я,J), Так что, если мое подозрение верно, то вы можете ускорить его до , отслеживая список непустых позиций для каждого значения i и используя список для i - 2, чтобы ускорить вычисление списка для i .О(N)яя-2я

Если вы храните в массиве, пространство все равно будет равно O ( n log n ) даже после ускорения, но это можно улучшить, используя вместо этого хеш-таблицу. Или же вы можете хранить F в битовом массиве с O ( n ) log n- битными словами (используя замечание, что вам нужно только знать, пусто оно или нет; вы можете найти два символа для каждой подстроки, посмотрев на первые две его позиции во входной строке).FО(NжурналN)FО(N) журналN

Дэвид Эппштейн
источник
Можете ли вы сказать мне, почему вы думали, что динамическое программирование будет лучшим выбором для этой проблемы? Где мы столкнемся с проблемой, если будем использовать какое-либо статическое программирование, например C ?
Тарит Госвами
1
Динамическое программирование - это метод проектирования алгоритмов, а не класс языков программирования.
Дэвид Эппштейн