How to get all possible matches of std::regex

Question

I would like to find all possible matches of regex, how is it possible?

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;
}

Gives output:

0: 2
1: 2
2: 25

But can't find third 2: 2 exactly. I prefer to use regex because of O(n) complexity for searching several tokens at same time.

UPDATE:

Maybe split token list to non-prefixable lists and create several regexes? For example: (2|4|25|45|251|455|267) => (2|4), (25|45|267), (251|455) This will grow complexity to something like O(n log(m))

UPDATE 2:

Please, provide short STL-based algorithm of splitting token vector to non-prefixable vectors to answer this question.

Answer 1

I dont think it's possible with an iterator and a single regexp. Here's how it works.

Your regexp searches for a substring that is either "2" or "25". Now, you start the search with sregex_iterator. It starts with the first symbol of the string, and tries to find match with your regular expression. If there is a match, it is "recorded", and the iterator is advanced to the position after the match. If there is no match, the iterator is advanced 1 position forward. This process continues until the end of the string is reached.

Now, each time it finds a match it will try to find the best (i.e., longest) match from your regular expression. So if a substring matches both 2 and 25, it will take 25 since it's longer. So I'd say you need 2 regular expressions.

Answer 2

You can't obtain the third '2', because regexes always return the longest match. In order to get "all the possible matches" you need to run the query two times, since 2 is contained in 25.