文字列の部分検索

Question

私のアプリケーションでは、高速検索のためのインデックスとして使用される一連のキーがあります。

現時点では完全な文字列を検索することができますが、文字列のどこでも発生する部分文字列を検索することができれば最大の柔軟性が得られます。もちろん、これを行う単純な方法は、リスト内のすべての文字列を繰り返し処理し、サブ文字列を探すことです。これはうまくいくが、リストが成長し始めるには遅すぎるだろう。

私は基数の木について少し読んでいますが、これは文字列の最初から部分一致を行うことができるだけで、文字列の最後からも可能です。

私の質問は、部分一致の問題（1つの大きな文書ではなく）を解決するために、文字列のリストで調べる必要があるアルゴリズムです。並べ替えられた文字列のリストを保持していれば、この問題は簡単でしょうか？文字列が同じ長さであっても可変長の文字列の場合は、これが簡単になることがわかります。私は合理的なアプローチを思いつくことができませんでした。

Answer 1

大きな文字列の中に文字列がすべて含まれていて、その中に特定の区切り文字がある場合はどうでしょうか？索引の部分文字列、部分文字列の索引を検索し、区切り文字で分割します。これで文字列の索引が作成されました。すべてのマッチを見つけるために正規表現を使用してください。

Answer 2

サフィックスツリーとサフィックス配列は、部分文字列マッチングをすばやく実行する場合に便利です。