Ответ заключается в том, чтобы построить суффиксные деревья для всех строк по отдельности, а затем пересечь их.Дерево суффиксов похоже на дерево, содержащее все суффиксы одной строки одновременно.
Построение дерева суффиксов для фиксированного алфавита составляет O(n) с алгоритмом Укконена .(Если вам не нравится это объяснение, вы можете использовать Google, чтобы найти других.) Если у вас есть m деревья размером n, это время O(nm).
Пересекающиеся суффиксные деревья - этоВопрос о том, чтобы пройти их параллельно, идти дальше только тогда, когда можно идти дальше по всем деревьям.Если у вас есть m деревья размером n, эту операцию можно выполнить за время, не превышающее O(nm).
Общее время этого алгоритма - время O(nm).Учитывая, что простое чтение строк имеет время O(nm), вы не можете сделать это лучше.
Добавляя небольшое количество деталей, предположим, что ваше дерево суффиксов написано как один символ на узел,Таким образом, каждый узел - это просто словарь, ключи которого являются символами, а значения - остальной частью дерева.Так что для нас ваш пример, для строки ABABA диаграмма в https://imgur.com/a/tnVlSI1 превратится в структуру данных, что-то вроде (см. Ниже) этого:
{
'A': {
'B': {
'': None,
'A': {
'B': {
'': None
}
}
}
},
'B': {
'': None
'A': {
'B': {
'': None
}
}
}
}
И аналогично BABAпревратится в:
{
'A': {
'': None
'B': {
'A': {
'': None
}
}
},
'B': {
'A': {
'': None,
'B': {
'A': {
'': None
}
}
}
}
}
Со структурами данных, которые выглядят так, наивный Python для их сравнения выглядит так:
def tree_intersection_depth (trees):
best_depth = 0
for (char, deeper) in trees[0].items():
if deeper is None:
continue
failed = False
deepers = [deeper]
for tree in trees[1:]:
if char in tree:
deepers.append(tree[char])
else:
failed = True
break
if failed:
continue
depth = 1 + tree_intersection_depth(deepers)
if best_depth < depth:
best_depth = depth
return best_depth
И вы бы назвали это tree_intersection_depth([tree1, tree2, tree3, ...]).
С этими двумя деревьями это действительно дает 3 в качестве ответа.
Теперь я фактически обманул, выписывая эту структуру данных.Что делает суффикс-деревья эффективными, так это то, что у вас на самом деле нет структуры данных, которая выглядит так.У вас есть тот, который повторно использует все повторяющиеся структуры.Таким образом, код для имитации настройки структур данных и их вызова выглядит следующим образом:
b_ = {'B': {'': None}}
ab_ = {'': None, 'A': b_}
bab_ = {'B': ab_}
abab = {'A': bab_, 'B': ab_}
a_ = {'A': {'': None}}
ba_ = {'': None, 'B': a_}
aba_ = {'A': ba_}
baba = {'B': aba_, 'A': ba_}
print(tree_intersection_depth([abab, baba]))
И теперь мы можем видеть, что для получения обещанной производительности есть пропущенный шаг.Проблема в том, что, хотя размер дерева составляет O(n), при его поиске мы потенциально можем посетить O(n^2) подстрок.В вашем случае вам не нужно беспокоиться об этом, потому что подстроки гарантированно никогда не пойдут на глубину более 60. Но в общем случае вам нужно добавить памятку, чтобы при рекурсии сравнивались структуры данных, которые вывидели раньше, вы сразу возвращаете старый ответ, а не новый.(В Python вы бы использовали метод id() для сравнения адреса объекта с теми, которые вы видели раньше. В C ++ для этой же цели есть набор кортежей указателей.)