使用C++中的RegEx查找具有優化迭代次數的模式

考慮以下兩種情況，在這兩種情況下，要測試的字符串在任何組合中只包含字符'a'，'t'，'g'和'c'並且可以是任意長度的。例如，它可能只有't'。使用C++中的RegEx查找具有優化迭代次數的模式

測試以查看「a」是否發生超過5次。如果字符串的長度爲100，並且字符'a'在前10個位置出現五次，則正則表達式不應搜索剩餘的字符串。
測試以查看零個或多個連續的'a'是否只出現一次，並且該字符串不能以'a'結尾。有效示例：ggtcccccccctggtaaaatcg，gctgctcgtccttgcttcg，ag。無效：a，agatcttgcgt，agtcga。

現在我知道如何構造一個基本的正則表達式來測試這兩種情況，但我想確保搜索是優化的，不會浪費不必要的迭代。在上面的第二點，agatcttgcgt應該在第三個字符被測試後立即終止，因爲它違反了連續規則。

對優化正則表達式的幫助將有所幫助。此外，不是主要問題，但我怎麼能看到如何執行搜索的內部（迭代次數等）？

2012-08-24 Raheel Khan

我懷疑，這將是「更好的優化，」把它寫在幾個語句，這可能包括多個正則表達式和/或其他運算符。在任何情況下，分析都是按順序進行的。不要忘記考慮環境因素，因爲它可能會消除當地的效率提升。 – 2012-08-24 00:18:30

您需要獲得Jeffrey Friedl的[_Mastering Regular Expressions，3rd ed._]（http://shop.oreilly.com/product/9780596528126.do）的副本。創建不涉及回溯的正則表達式涉及一些技巧。弗裏德爾深入瞭解事物。 –

如果性能很關鍵，您可能需要考慮非正則表達式解決方案。例如，您的第一個要求可以通過使用string.Contains輕鬆解決。

正則表達式通常以線性方式從左到右掃描輸入，查看每個字符直到找到匹配，並且如果有回溯，可能會多次查看字符。另一方面，存在一些高級的string searching algorithms，其可以在不必檢查字符串中的所有字符的情況下確定子字符串的存在或不存在。例如，要搜索aaaaa，只需檢查每五個字符，直到找到一個a。

此外，不是主要問題，但我怎麼能看到如何執行搜索的內部（迭代次數等）？

您可以使用使用RegexBuddy調試正則表達式和看多少步需要：

RegexBuddy: debugging a regex

來源

2012-08-24 00:14:41

使用C++中的RegEx查找具有優化迭代次數的模式

回答

相關問題