動的プログラミングや接尾辞ツリーを持たない最長共通部分文字列

Question

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

Answer 1

最初の（短い）文字列sに開始位置iが固定されているとします。今すぐもっと長い文字列の中で可能な限り長い接頭辞を見つけましょう。文字列s[i:] + # + tのprefix function（またはz function）を調べてO(n + m)で行うことができます。＃はsとtのいずれにも存在しない特殊記号です。

全体的な複雑さは、O(nm)もしN <メートル

O(n(n + m))であります