нахождение LCP двух строк в постоянном времени и линейном пространстве

Вот в чем проблема:
Предположим, S — это набор строк, и мы знаем общую длину всех строк в S в n. Мы должны найти структуру данных с пробелом O(n), которая находит LCP(s,t) в O(1), где LCP является самым длинным общим префиксом между строками с,т.


Сначала я думал, что смогу использовать хеширование, так как мы можем проверять числа за постоянное время и находить подстроки за постоянное время, если предварительно хешируем строки. Но я не думаю, что это сработает, так как требуется больше места и после небольшого поиск я обнаружил, что решение, вероятно, заключается в использовании массивов Trie, Suffix и, возможно, LCA и RMQ. Я думаю, что близок к ответу, но не знаю, как эти концепции могут работать вместе, чтобы создать структуру данных, обеспечивающую быструю работу LCP!


Спасибо за прочтение


prefix algorithm data-structures
person FrastoFresto    schedule 03.01.2020    source источник
comment
Можем ли мы предположить, что длина каждой строки равна sqrt(n) и что имеется sqrt(n) строк?   -  person Yonlif    schedule 03.01.2020
comment
@Yonlif Я так не думаю. мы просто знаем, что общая длина всех из них равна n   -  person FrastoFresto    schedule 03.01.2020
comment
Я думал о тяжелом легком разложении со строками длиннее sqrt(n).   -  person Yonlif    schedule 03.01.2020
comment
@Yonlif нравится сжимать файл?   -  person FrastoFresto    schedule 03.01.2020
comment
Что такое с и т? Потому что если это строки, то вы даже не сможете распознать их за постоянное время. Если это что-то, что можно сопоставить с внутренними узлами за постоянное время, то вы можете выполнить запрос LCA для дерева.   -  person Matt Timmermans    schedule 03.01.2020
comment
Попытка сделает это в O(length of prefix). Учитывая, что вы не можете построить строку для возврата быстрее, я думаю, что это должен быть ответ. Есть ли где-нибудь в исходном описании такая фраза, как строки фиксированной длины?   -  person btilly    schedule 03.01.2020
comment
Так будет ли разрешено использовать любой O(....) для заполнения этой структуры данных данными?   -  person Lasse V. Karlsen    schedule 04.01.2020
comment
Ответом на это утверждение будет «Да, это звучит как хороший план!». А потом, если кто-то спросит, что это за структура данных? Я бы ответил: О, вы задавали вопрос? Вы вообще смотрели Jeopardy?   -  person Lasse V. Karlsen    schedule 04.01.2020

Ответы (1)


arrow_upward
1
arrow_downward

Думаю, я знаю ответ, который они ищут.

Сначала создайте trie для всех строк. Каждый узел в дереве может включать указатель на строку, начинающуюся с этого префикса, и длину. Сопоставьте каждую строку с последним узлом в дереве, на котором заканчивается эта строка.

Теперь, когда дана пара строк (которая, по-видимому, вам сообщается как строка i и строка j), проблема возврата строки заключается в поиске наименьшего общего предка, а затем возвращении пары (pointer_to_start_of_string, length).

Но дерево может быть записано в виде дерева, а затем офлайновый самый низкий алгоритм общих предков Tarjan (см. https://www.geeksforgeeks.org/tarjans-off-line-lowest-common-ancestors-algorithm/) можно использовать для предварительной обработки этого дерева, чтобы очень быстро ответить на вопросы LCA. .

Технически это не O(1). Однако именно O(inverse_ackermann(n)) можно рассматривать как довольно маленькую константу для любого компьютера, вписывающегося в наблюдаемую вселенную.

person btilly    schedule 03.01.2020
comment
LCA Траяна — это автономный алгоритм, который не может отвечать на произвольные отдельные запросы за это время, даже после предварительной обработки. Есть способ сделать это за постоянное время после предварительной обработки с линейным пространством, используя обход Эйлера по дереву, чтобы свести проблему к запросу с минимальным диапазоном. См. geeksforgeeks.org/find-lca-in-binary- дерево-использование-rmq и en.wikipedia.org/wiki/Range_minimum_query - person Matt Timmermans; 04.01.2020