正則表達式：與DFA搜索（而不是匹配）

Question

我一直在關於正則表達式匹配器搜索模式背後的理論。所以，說我有一個匹配aab的正則表達式，如果不是在字符串開頭的match，我希望能夠從字符串的任何位置開始執行此匹配。我的意思是 - 在匹配模式下，我只能驗證字符串aab與一個正則表達式是否一致，另一方面是search這應該與產生相應跨度結果的aaab一起工作。 所以超級特別的 - 是否有任何方法來構建DFA searcher，或者這是根本不可能的，因爲它需要額外的內存，你不能在DFSM中擁有。很顯然，通過在for循環中重新應用matcher來輸入字符串，您實際上可以從matcher構建searcher，但這種方法的複雜性類似於O（len_of_pattern * len_of_input）。

Answer 1

我想你基本上回答了你自己的問題。像現代正則表達式實現中的許多其他功能一樣，搜索利用內存奇蹟來執行有限自動機不可行的事情。由於這需要內存，因此DFA傳統上無法循環字符串或沿輸入回溯。搜索需要能夠找到一個匹配，然後瞭解匹配如何匹配字符串。

Answer 2

正則表達式搜索器基本上與正則表達式匹配器相同，.*附加在表達式的前面。