c - 多数の文字列セット内の最長の部分文字列

Question

テキスト文字列の巨大な固定ライブラリと、頻繁に変更される入力文字列があります。ライブラリ内の任意の文字列から s までの最長一致部分文字列を、文字列 s の先頭から最短時間で見つける必要があります。完璧な世界では、ライブラリから次に長い一致、次に最適なものなども返します。これは、最長の共通文字列の問題ではありません。ライブラリ内のすべての文字列に対して最長の共通文字列を探しているわけではありません...膨大なライブラリ内の s と各文字列の間のペアごとに最適な部分文字列ができるだけ早く必要です。

Answer 1

読み直した後、これを行う最善の方法はおそらく、文字列の大きなライブラリのトライまたはプレフィックスツリーを構築し、それsに対して照合することだと思います。

これにはいくつかの利点があります。まず、大きなライブラリを (少なくともある程度) 圧縮された形式で保存します。次に、最長のものだけでなく、特定の入力に一致するすべての文字列を多かれ少なかれ自動的に通知します。

また、ユースケースにも非常によく適合します-入力からトライまたは（特に）プレフィックスツリーを構築するにはかなりの作業が必要ですが、後でそれを使用すると非常に高速です。

Answer 2

事前にリストを並べ替え (つまり、コンパイル時またはそれ以前)、bsearch を使用します。

http://www.cplusplus.com/reference/clibrary/cstdlib/bsearch/

マッチを見つけたら、近くを前後に見て、好きなだけ「マッチ」を取得できます。

ところで、bsearch はコンパレータ関数を通過するため、必ずしも最速ではありませんが、標準 C ライブラリに含まれています。