Найти максимальную входную строку, соответствующую регулярному выражению

Question

Учитывая регулярное выражение re и входную строку str, я хочу найти максимальную подстроку str, которая начинается с минимальной позиции, которая соответствует re.

Особый случай:

re = Regex("a+|[ax](bc)*"); str = "yyabcbcb"

соответствие re с str должно вернуть совпадающую строку "abcbc" (и не "a", как PCRE делает). Я также имею в виду, что результат будет таким, каким я хочу, если порядок чередований меняется.

Answer 1

Варианты, которые я нашел, были:

1. POSIX расширенный RE - вероятно, устарел, используется egrep...
2. RE2 от Google - с открытым исходным кодом RE2 - C++ - также доступна C-оболочка

Answer 2

С моей точки зрения, у вашего вопроса две проблемы.

Во-первых, при изменении порядка чередования результаты должны измениться.

Для каждого символа "a" в строке он может соответствовать "a+" или "ax*". Таким образом, сопоставление 'a' с изменениями в вашем регулярном выражении неоднозначно.

Во-вторых, для нахождения максимальной подстроки требуется шаблон совпадения самого длинного совпадения. Насколько мне известно, только RE2 предоставляет такую ​​функцию, о чем упоминал @Cosinus.

Поэтому я рекомендую разделить "a+|ax*" на два регулярных выражения, найти в каждом из них максимальную подстроку, а затем сравнить позиции обеих подстрок.

Чтобы найти самое длинное совпадение, вы также можете обратиться к описанию предыдущего сообщения с регулярным выражением здесь. Основная идея состоит в том, чтобы искать подстроки, начиная с позиции строки 0 до len(str), и отслеживать длину и позицию при нахождении совпадающих подстрок.

PS Некоторые языки предоставляют функции регулярных выражений, аналогичные findall(). Будьте осторожны при их использовании, так как результаты могут быть неперекрывающимися. И неперекрывающиеся совпадения не обязательно содержат самую длинную совпадающую подстроку.