私は、AND演算子とOR演算子とワイルドカードを持つパターンの文字列のリストを持っています。入力文字列が与えられたら、パターンと一致する場合はtrueを返し、一致しない場合はfalseを返します。文字列をいくつかのパターンにマッチさせる最速の方法
私は 'n'パターンと長さ 'm'のクエリを持っています 今、明白な方法は、文字列の各パターンに対してループとgrepを実行することです。これにはO（nm）時間がかかります。
今、私の質問は、より良いことが可能なのでしょうか？多分私は、ある種の表現評価有限状態機械を考えていたでしょうか？そのようなものの名前/参照の実装はありますか？
ありがとうございました
あなたはBoyer–Moore string search algorithmを探しています。
パターンを最初に解析してAbstract Syntax Treeをビルドした後、クエリ文字列を別の抽象構文ツリーに解析してから、ノード検索（ルート用）を使用すると良い結果を得ることもできます。あなたのパターン文字列があなたのクエリ文字列内に見つかったかどうかを知るために、単純なツリー比較アルゴリズムを使います。理論的には、クエリ文字列の解析はO（n）で行うことができますが、実際にはパフォーマンスが向上するとは思っていません。それは面白いエクササイズかもしれません。
私はあなたがOPを誤解したと思います。私はOP *が検索されているものを参照するために "パターン"を使用していると思います。私は、多くの文字列から検索まで、そして文字列から検索までの文字列が1つしかないと思います。 （また、 "パターン"は単純な部分文字列よりもはるかに複雑なようです。） – ruakh
@ruakhそうです。私は答えを言い直します。 –
（最近のCPUは、ループがオンチップメモリに収まり、分岐予測が可能な場合には、特に線形データ構造上で高速にループしていることに注意してください）、メモリアクセスのためにポインタに追従してオフチップに移行する速度がはるかに遅くなります。あなたが何をしようとしても、ダムでブルートフォースのアルゴリズムに対してベンチマークを行うべきです。 –
すべてのパターンからマージされた検索を処理する有限状態マシンを作成できます。 RegExをFSMに変える方法については、http://stackoverflow.com/questions/525004/short-example-of-regular-expression-converted-to-state-machineを参照してください。 –