正規表現：DFAと一致するものの代わりに

Question

私はregex matcherの検索モードの背後にある理論について疑問に思っています。だから、aabに一致する正規表現を持っているとしたら、文字列の先頭にmatchの代わりに何か文字列の任意の位置から始まるこの一致を実行できるようにしたいとします。つまり、マッチモードでは、文字列aabが正規表現と一貫していることを確認できますが、searchではaaabの対応するスパン結果が生成されます。 スーパー特有のことですが、DFA searcherを構築する方法はありませんか、DFSMには追加できないメモリが必要なため、これは基本的に不可能です。実際にはmatcherからmatcherをforループの入力文字列に再適用することによってsearcherを構築することはできますが、そのようなアプローチの複雑さはO（len_of_pattern * len_of_input）のようなものです。

Answer 1

あなたは基本的に自分の質問に答えたと思います。検索は、現代の正規表現実装の他の多くの機能と同様に、メモリの驚異を利用して有限オートマトンで実現不可能なことを行います。 DFAは従来、メモリを必要とするため、文字列をループしたり、入力に沿ってバックトラックすることができませんでした。検索には一致を見つけ、その一致が文字列にどのように適合するかを理解する能力が必要です。

Answer 2

正規表現サーチャは基本的に正規表現マッチャーと同じものですが、式の前には.*が付いています。