Идея из главы 32. «Поиск простых чисел с помощью регулярных выражений» сработает и на этот раз, но на этот раз не для проверки делимости одного числа на другое, а для решения линейного диофантова уравнения. Нужно сопоставить специально подготовленную строку из одинаковых символов (хотя бы тех же самых букв Q) со специально подготовленным регулярным выражением.

Длина специально подготовленной строки — это число в правой части уравнения (последний параметр командной строки).

А теперь перейдём к регулярному выражению.

Разрешимость уравнения — это возможность разбить строку из $b$ символов на группы, длины которых в символах равны слагаемым из левой части уравнения: $l_i=a_i{x}_i$. Если такое разбиение возможно, значения неизвестных легко найти: $x_i=\frac{l_i}{a_i}$.

Проиллюстрируем сказанное на примере уравнения $5x+11y=37$:

◄─────────────────37────────────────►
QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ
◄──────15─────►◄─────────22─────────►

Всё, что требуется от двух символьных групп в этом примере — это чтобы их длины были бы кратными соответственно $5$ и $11$. Эти группы соответствуют регулярным выражениям (Q*)\1{4} и (Q*)\1{10}. Вся же строка, составленная из 37 букв, должна соответствовать, от начала до конца, шаблону ^(Q*)\1{4}(Q*)\2{10}$. Этот шаблон начинается и заканчивается значками привязки к началу и концу строки, а между ними расположены однотипные фрагменты вида (Q*)\$i${$a_i-1$}, где $i=1,\dots ,n$.

До сих пор нам приходилось пользоваться неизменными, заранее записанными в тексте программы шаблонами регулярных выражений. Теперь понадобились шаблоны, не определённые заранее. Можно ли нужный шаблон составить во время выполнения программы, а не на этапе её написания? Можно. Поскольку в шаблоне могут использоваться переменные, нужно заранее, до осуществления поиска, сформировать строку с шаблоном, а затем поместить её в оператор поиска.

Итак, успешность сопоставления с регулярным выражением означает наличие целого неотрицательного решения у уравнения, а неудача при сопоставлении — отсутствие таких решений. А как же найти само решение? Числа $x_1,x_2,x_3,\dots$ окажутся равными соответственно длинам (в символах) переменных $1, $2, $3, … Значения этих переменных, напомним, содержат части строки, захваченные группами захвата в регулярном выражении. Нам потребуется перебор в цикле этих переменных, и это представляет некоторую проблему. В следующем разделе мы разберёмся с этой трудностью.