substring - 文字列のすべての部分文字列に対してサフィックス Trie を作成する方法は?

Question

文字列のすべての部分文字列に対して、スペース効率の良いサフィックス トライを作成したいと考えています。文字列の長さが 5000 であると仮定すると、部分文字列の数は約 25*10^6 になり、ノードごとにサイズ 26 の linkd の配列が格納されるため、合計メモリ = 26*5000*5000 となり、実行時エラーが発生します。期待されています。スペース効率の良い接尾辞トライの解決策を手に入れました。ここでは、スペースの順序がほぼ線形になるように、選択の余地のないパスを圧縮します。しかし、私は理解できないので、誰かがこれから私を助けることができます.

Answer 1

トライを検索するのではなく、接尾辞ツリーを検索すると思います。パスを圧縮することも方法の 1 つですが、Ukkonen アルゴリズムを検索するだけです。時間と空間の複雑さは n です。より理解しやすいものが必要な場合は、Suffix Arrays を検索してください。空間の複雑さも n であり、定数が低く (32 かそこらではなく約 6 です。正確な数字は覚えていません)、ハードウェアによるキャッシュ予測がはるかに優れています。