2 つの文字列の最長の共通部分文字列を見つけたい場合、時間/空間の複雑さの点でどのアプローチがより効率的でしょうか: DP の接尾辞配列を使用しますか?
DP は、O(m*n) 時間の複雑さで O(m*n) スペースを発生させます。サフィックス配列アプローチの時間の複雑さはどうなりますか?
1) 接尾辞 O(m) + O(n) を計算する 2) それらを並べ替える O(m+n log2(m+n)) 3) m+n-1 文字列の最も長い共通接頭辞を見つける? [#of comparisons の計算方法がわからない]
接尾辞配列を使用すると、部分文字列を使用してさらに多くのことを実行できます (部分文字列の検索など)。ただし、この場合、残りの機能は必要ないため、DP はより簡単でクリーンなアプローチと見なされますか? 2 つの文字列を比較する場合に使用する必要がありますか?
また、文字列が 2 つ以上ある場合はどうなるでしょうか。