1
Skienaのアルゴリズム設計マニュアル質問8-3パートBは、動的プログラミングに依存しない最も長い共通部分文字列を見つけるための "より単純な" BigO(nm)アルゴリズムを提供するよう求めます。明らかな答えはサフィックスツリーを使用するようですが、Skienaは「Simpler」という言葉を使用します。接尾辞ツリーがDPより簡単であるとは思わないでしょう。おそらく検索は簡単ですが、シンプル。ですから、O(nm)時間でこの問題を解決する別の方法があるのでしょうか?動的プログラミングや接尾辞ツリーを持たない最長共通部分文字列