trie を使用して、2 つ以上の文字列の中から LCS (最長の共通部分文字列) を見つけるにはどうすればよいですか?
私の最初の文字列が「abbcabdd」だとします。次に、最初に「abbcabdd」をトライに挿入し、次に「bbcabdd」、次に「bcabdd」....、次に「d」を挿入し、すべての文字列に対してこのプロセスを繰り返します。
次に、トライをたどって最長の部分文字列を計算します。
しかし、効率的ではないと思います。他に改善された方法はありますか？
2887 次
1 に答える
4
あなたが説明しているのはまさにサフィックスツリーです- サフィックスツリーを生成するために最適化されたアルゴリズムを使用すると、効率が向上します!
接尾辞ツリーを構築するためのアルゴリズムがあることに注意してくださいO(n)(もちろん、一定のアルファベットを想定しています)。
于 2012-10-16T22:44:58.907 に答える