Регулярное выражение с перекрытием и повторением

Question

Предположим, у меня есть строка s = "ACBCAACBCBCAB". Я хотел бы найти регулярное выражение, которое может дать мне ВСЕ строки длиной 3, которые повторяются как минимум 2 раза в s (возможно, с перекрытием). Например, строка s дает:

ACB (2 раза)

CBC (3 раза)

BCA (2 раза)

Я думаю использовать regex = "(?=([ABC]{3}))\1{1,}", но это не совсем правильно. Я использую C ++.

Спасибо.

PS: s в вопросе является примером. Я хотел бы регулярное выражение, которое работает для общего s (подстроки, длина 3, все еще повторяются по крайней мере 2 раза). Другой пример - когда s = "ABABA", подстроки имеют значение "ABA".

Answer 1

Если вы сопоставили регулярное выражение

(?=(.{3}))(?=.+\1)

со строкой

ZABABABCACACABAABADEFGDEF

, было бы 7 совпадений (из пустых строк), где содержимое группы захвата 1 для каждого совпадения 3-буквенные строки, показанные ниже.

ZABABABCACACABAABADEFGDEF
0123456789012345678901234
 ABA
  BAB
   ABA
       CAC
        ACA
            ABA
                  DEF

Демонстрация

Каждая из этих трехсимвольных строк сопровождается одними и теми же 3-значными символами, появляющимися хотя бы один раз в остаток строки. В результате некоторые совпадения повторяются. Поэтому мы должны извлечь уникальные значения массива

["ABA", "BAB", "ABA", "CAC", "ACA", "ABA", "DEF"] 

, чтобы получить

["ABA", "BAB", "CAC", "ACA", "DEF"] 

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

Первое совпадение (?=(.{3})) происходит, когда внутренний указатель механизма регулярных выражений находится непосредственно перед Z, а группа захвата 1 содержит ZAB. Теперь мы ищем совпадение содержимого группы захвата 1 позже в строке, начиная справа после the Z. По этой причине нам нужно .+, а не .* в (?=.+\1). Нет совпадения (?=.+\1), поэтому совпадение не удалось. Поскольку обходные пути не потребляют символов, внутренний указатель механизма регулярных выражений не сместился.

Затем внутренний указатель перемещается на один символ вперед на место непосредственно перед первым A, и содержимое группы захвата 1 становится ABA. Найдено совпадение, начиная со второго A со смещением 3, после чего внутренний указатель снова перемещается на один символ вперед на место непосредственно перед первым B, и процесс повторяется.

* 1039 Предположим, что вместо него использовалось регулярное выражение

(?=(.{3})).+\1

. После того, как ZAB появляется только один раз в строке, указатель находится перед первым A, а группа захвата 1 содержит ABA. .+\1 затем соответствует ABABABCACACABAABA (показывая, что ABA повторяется). Однако внутренний указатель затем перемещается в местоположение непосредственно перед первым D, в результате чего мы пропускаем несколько 3-символьных строк, которые повторяются. Помогает .+ не жадный ((?=(.{3})).+?\1, но мы все еще скучаем по BAB и ACA.