C:正则表达式优化 |保存状态

Question

假设我想搜索“AAAAAAAABBBBBBB”和“AAAAAAAACCCCCCCCCC”。我搜索模式“(AB|AC)”。

有没有办法在搜索“AAAAAAAA”部分然后分别继续搜索[B..]和[C..]部分后保存搜索状态？所以我只需要在 [A..] 中搜索一次。

我写了一个简短的伪代码示例以更加清晰。

第一步:

pattern = "(AB|AC)"
match("AAAAAAAA", pattern)
save_state()

第二步:

match("BBBBBBB", pattern) 

如果查找匹配“AB”

第三步:

restore_state()
match("CCCCCCCCCCC", pattern) 

应该找到匹配的“AC”

Answer 1

如果您使用使用(真正的)NFA/DFA 方法的正则表达式风格(例如 RE2 )，则不必存储某些内容，因为每个输入字符仅(或应该)仅使用一次(这可以没有好转)。

如果您的风格使用回溯算法，那么您可能会很幸运。其中一些引擎允许您使用 (?>x) 或 x{1}+ (其中 { 1} 可以是任何量词)

所以就你的情况而言，可能是(如果允许的话)

(?>A)(B|C)

或

A{1}+(B|C)