n個の文字列の明確なサブ文字列の数を調べる方法は？

Question

各n文字列がlength <=10^5であるとします。

入力：“aa ab ac ad”

出力：8(“a”,”b”,”c”,”d”,”aa”,”ab”,”ac”,”ad”)

入力：“aab bcd”

出力：10(“a”,”b”,”c”,”d”,”aa”,”ab”,”bc”,”cd”,”aab”,”bcd”)

更新：

SU ffixツリーは1つの解決策です。しかし、それはより多くのメモリを必要とします。

接尾辞ツリー以外の解決法はありますか？

私は試みましたが、この問題を効率的に解決するアルゴリズムは見つかりませんでした。

Answer 1

接尾辞ツリー。サフィックスツリーを設定する以外に何もする必要はありません。それは、正確には、任意の文字列または文字列のすべての別個の部分文字列をリストする構造体です。