403
правки
Изменения
→Модификация
Так как мы храним указатель, где находится состояние в двусвязном списке, то операцию перемещения состояния из одного класса в другой можно выполнить за <tex>O(1)</tex>.
Чтобы эффективно находить множество <tex>Inverse</tex>, построим массив <tex>Inv</tex>, который для состояния <tex>r</tex> и символа <tex>a</tex> в <tex>Inv[r][a]</tex> хранит множество состояний, из которых существует переход в <tex>r</tex> по символу <tex>a</tex>. Так как наш алгоритм не меняет изначальный автомат, то массив <tex>Inv</tex> можно построить перед началом основной части алгоритма, что займет <tex>O(|\Sigma| |Q|)</tex> времени.
Для быстрой проверки, находится ли пара <tex>(C,a)</tex> в очереди <tex>S</tex>, будем использовать массив <tex>InList</tex> размера <tex>|Q| \times |\Sigma|</tex>, где <tex>InList[C][a] = true</tex>, если пара <tex>(C,a)</tex> содержится в очереди.
