c++ - 如何获得 std::regex 的所有可能匹配项

Question

我想找到正则表达式的所有可能匹配项，这怎么可能？

regex rx("(2|25)");
string s = "2225";
for (sregex_iterator it(s.begin(), s.end(), rx), end; it != end; ++it) {
    cout << it->position() << ": " << it->str() << endl;
}

给出输出:

0: 2
1: 2
2: 25

但找不到第三个 2: 2。我更喜欢使用正则表达式，因为 O(n) 同时搜索多个标记的复杂性。

更新:

也许将标记列表拆分为不可前缀的列表并创建多个正则表达式？例如:(2|4|25|45|251|455|267) => (2|4), (25|45|267) , (251|455) 这会增加复杂度，比如 O(n log(m))

更新 2:

请提供简短的基于 STL 的将标记 vector 拆分为不可前缀 vector 的算法来回答这个问题。

Answer 1

我认为使用迭代器和单个正则表达式是不可能的。这是它的工作原理。

您的正则表达式搜索“2”或“25”的子字符串。现在，您可以使用 sregex_iterator 开始搜索。它从字符串的第一个符号开始，并尝试找到与您的正则表达式匹配的内容。如果有匹配，则“记录”，迭代器前进到匹配后的位置。如果没有匹配项，则迭代器向前推进 1 个位置。这个过程一直持续到到达字符串的末尾。

现在，每次找到匹配项时，它都会尝试从您的正则表达式中找到最佳(即最长)匹配项。因此，如果一个子字符串同时匹配 2 和 25，则需要 25，因为它更长。所以我会说你需要 2 个正则表达式。