Приближенное сравнение регулярных выражений: различия между версиями

Теперь возьмем все поддеревья R, максимальный размер которых не превышает r, и предварительно обработаем их при помощи вышеприведенной техники. Преобразуем каждое такое поддерево в лист в R, помеченный специальным символом <math>a_A</math>, ассоциированным с соответствующим небольшим НКА A. Если в R нет последовательных замыканий Клини, которые можно упростить как R** = R*, то размер R после этого преобразования составит O(m/r). Обозначим преобразованное регулярное выражение за R'. В сущности, к R' применяется техника теоремы 1, которая говорит о том, как обращаться с особыми листьями, соответствующими небольшим НКА. Эти листья при помощи построения Томпсона преобразуются в две вершины, соединенных с ребром с меткой <math>a_A</math>. Когда процесс распространения стоимости пути достигает вершины-источника ребра с меткой <math>a_A</math> со стоимостью c, необходимо обновить счетчик начального состояния НКА A до c (или k + 1, если c > k). Затем с помощью таблицы «метода четырех русских» можно выполнить все операции распространения стоимости в пределах A за константное время и, наконец, получить в счетчике конечного состояния A новое значение для целевой вершины ребра, помеченного <math>a_A</math>, в НКА верхнего уровня. Таким образом, все ребра (обычные и особые) НКА верхнего уровня могут быть пройдены за константное время, поэтому с помощью теоремы 1 стоимости в <math>G_i</math> можно получить за время O(mn/r). После этого стоимости переносятся в <math>G_{i + 1}</math>, используя таблицы «четырех русских» для получения текущих значений счетчиков каждого подграфа <math>G_{i + 1}</math>.