В моем старом учебнике по чешскому алгоритму я столкнулся со следующей проблемой, к сожалению, без подсказок и решений.
«Мы определяем слова Фибоначчи как , , , где и - общие буквы. Как в данном строка (над потенциально большим алфавитом) вы можете найти самое длинное подслово Фибоначчи за линейное время? "F 1 = b F n + 2 = F n F n + 1 a b
Я знаю решение в квадратичном времени, но не могу свести его к линейному. Кто-нибудь может указать мне правильное направление?
Ответы:
Очевидный путь - динамическое программирование: пусть хранит две буквы, для которых слово порядка Фибоначчи i начинается с позиции j , и вычисляет это, рассматривая F ( i - 2 , j ) и F ( i - 1 , j + fib ( i ) ) . Это занимает не более O ( n log n ) времени, поскольку существует только логарифмически много возможных значений iF( я , j ) я J F( i - 2 , j ) F( i - 1 , j + fib( я ) ) O ( n logн ) я ,
Но я подозреваю, что могут быть только позиции для которых F ( i - 2 , j ) непуста (то есть, что при наличии двух слов Фибоначчи одинаковой длины они могут перекрываться только до постоянная доля их длины, а не большая часть их длины). Непустые позиции F ( i - 2 , j ) - единственные, для которых вам нужно вычислить (постоянное время) для F ( i , j )O ( н / фиб( я ) ) F( я - 2, j ) F( я - 2 ,j ) F( я , j ) , Так что, если мое подозрение верно, то вы можете ускорить его до , отслеживая список непустых позиций для каждого значения i и используя список для i - 2, чтобы ускорить вычисление списка для i .O ( n ) я я - 2 я
Если вы храните в массиве, пространство все равно будет равно O ( n log n ) даже после ускорения, но это можно улучшить, используя вместо этого хеш-таблицу. Или же вы можете хранить F в битовом массиве с O ( n ) log n- битными словами (используя замечание, что вам нужно только знать, пусто оно или нет; вы можете найти два символа для каждой подстроки, посмотрев на первые две его позиции во входной строке).F O ( n logн ) F O ( n ) журналN
источник