如何確定正則表達式中的子字符串？

Question

我已經實現了用於模式搜索的trie，並且工作正常。使用這個trie我可以找到所有在O（n）複雜文本中呈現的關鍵字。

問題是我想爲我的模式（關鍵字）使用正則表達式，並希望找到文本中存在的所有關鍵字。

例如： 我寫[a-z0-9 \。] {6，30} \ @ [a-z0-9 \。] {2,12} \。[a-z0-9] { 2,6}找到電子郵件ID，它會提取我正確的東西，但它不會找到第一或第二塊下的子字符串。

例如我有文字爲。 examplegmail@gmail.com

和關鍵字：ample mail

在這個例子中這個表達式會告訴我的電子郵件ID的結束位置，但它不會告訴任何關於ample或mail關鍵字。

編輯：假設我有正則表達式爲一個*（？C | CD）+ 和DFA會是什麼樣子::

，現在我有一個像dfdfdacbcbbcb數據在這個數據它會告訴我在達到ac等在每個字符後的模式，但我怎麼才能知道結束模式的長度？

Answer 1

你的「trie」包含操作：「test for char」「分支到第n個子樹」。

添加另一個運算符來保存位置：「記住第N個字符索引」，它將當前字符位置寫入字符串指針數組的第n個插槽中。

將這些運算符插入到您的（抽象）trie規範中，編譯爲真正的trie，然後運行它。由於特里匹配器「匹配」匹配中的各種關鍵點，它可以在字符串緩衝區中記錄這些點。在最後的比賽中，你有一系列的指針（儘可能多的）到你的比賽的子部分。

對於示例：

[a-z0-9\.]{6, 30}\@[a-z0-9\.]{2,12}\.[a-z0-9]{2,6} 

想象我要挑文本左和中@的權利。

我添加位置運營商節約，這是我武斷地表示爲「＃N」：

#1[a-z0-9\.]{6, 30}#2\@[a-z0-9\.]{2,12}\.[a-z0-9]{2,6}#3 

這將（相當平凡）捕捉到起始位置時，「@」符號 的位置， （相當平凡）的最終位置，如位置1,2和3.當然，如果您覺得合適，您可以在中間更多。

[許多正則表達式系統在遇到分組操作符（...）時會隱式地執行此操作，從左到右對分組進行編號。這總是足夠的，因爲你總是可以在這樣的分組操作符中包裝一個有趣的子正則表達式。我喜歡明確的指示方案;閱讀器和模式匹配器很清楚它必須插入這些位置捕獲操作。我們已經實現了正則表達式匹配器，使用上面的#n符號。]。

如果您正在尋找各種各樣的關鍵字和相關文本，您的trie可能有很多選擇運算符。您可以在每個選擇分支的適當位置添加這些位置捕捉操作符，以挑選出與該關鍵字相關的信息。您可能需要添加另一個運算符「識別關鍵字k」，以幫助解釋模式匹配程序結果的代碼瞭解找到了哪些特殊關鍵字，從而瞭解如何解釋位置索引。