Я ищу структуру данных , которая хранит множество строк над набором символов , способных выполнять следующие операции. Обозначим через D ( S ) в качестве структуры данных , хранящей множество строк S .$\Sigma$$\mathcal{D}(S)$$S$

• Add-Prefix-Setна : для некоторого множества T (возможно, пустых) строк, размер которых ограничен константой, а длины строк ограничены константой, вернуть D ( { t s | t ∈ T , s ∈ S } ) , Оба эти константы являются глобальными Ограничивающими: они одинаковы для всех входов Т .$\mathcal{D}(S)$$T$$\mathcal{D}( \{ t s\ |\ t \in T, s \in S\} )$$T$
• Get-Prefixesна : возврат { a | a s ∈ S , a ∈ Σ } . Обратите внимание, что я действительно не против того, какая структура используется для этого набора, поскольку я могу перечислить его содержимое за O ( | Σ | ) время.$\mathcal{D}(S)$$\{ a \ | \ as \in S, a \in \Sigma \}$$O(|\Sigma|)$
• Remove-Prefixesна : вернуть D ( { s | a s ∈ S , a ∈ Σ } ) .$\mathcal{D}(S)$$\mathcal{D}( \{ s \ | \ as \in S, a \in \Sigma \} )$
• Merge: даны и D ( T ) , вернуть D ( S ∪ T ) .$\mathcal{D}(S)$$\mathcal{D}(T)$$\mathcal{D}(S \cup T)$

Теперь я действительно хотел бы выполнить все эти операции за время , но я в порядке со структурой, которая выполняет все эти операции за время o ( n ) , где n - длина самой длинной строки в состав. В случае слияния, я хотел бы, чтобы o ( n 1 + n 2 ) выполнялось, где n 1 - это n для первой, а n 2 - для n для второй структуры.$O(1)$$o(n)$$n$$o(n_1+n_2)$$n_1$$n$$n_2$$n$

Дополнительным требованием является то, что структура является неизменной или, по крайней мере, вышеуказанные операции возвращают «новые» структуры, так что указатели на старые по-прежнему функционируют, как и прежде.

Примечание об амортизации: это хорошо, но вы должны остерегаться настойчивости. Поскольку я все время использую старые структуры, у меня будут проблемы, если я столкнусь с наихудшим случаем с каким-то конкретным набором операций с той же структурой (игнорируя создаваемые им новые структуры).

Я хотел бы использовать такую ​​структуру в алгоритме синтаксического анализа, над которым я работаю; Приведенная выше структура будет содержать запрос, необходимый мне для алгоритма.

Add-Prefix-Set$O(1)$

$|\Sigma|$

Я думал довольно долго, но не нашел проблемы с выполнением всех ваших операций самым глупым из возможных способов в структуре структуры DAG, похожей на три:

Надстройка Приставка-Set

$T$

$O(|T|)$

Объединить

Объедините корни двух структур: сделайте все дочерние узлы второго корневого потомка первого узла. Теперь у вас может быть несколько ребер, помеченных одним и тем же символом, идущим от одного и того же узла.

$O(1)$

Ленивое обновление рута

1. $O(|\Sigma|)$$O(1)$
2. $O(1)$

Get-префиксы

Ленивое обновление рута. Теперь найдите всех потомков корня и сообщите множество букв по краям, идущим к ним.

$O(|\Sigma|)$

Remove-префиксы

Ленивое обновление рута. Объедините всех дочерних элементов корня и установите корневой указатель на результат этого объединения. Ленивое обновление нового рута.

$O(|\Sigma|)$

Упорство

$O(1)$$O(|\Sigma|)$$O(log N)$$N$