403
правки
Изменения
→Модификация
*<tex>Size</tex> {{---}} целочисленный массив, где <tex>Size[i]</tex> хранит количество состояний из класса <tex>i</tex>, которые содержатся в <tex>Inverse</tex>;
*<tex>Twin</tex> {{---}} массив, хранящий в <tex>Twin[i]</tex> номер нового класса, образовавшегося при разбиении класса <tex>i</tex>.
Сам же алгоритм обработки <tex>T'</tex> будет выглядеть так:
<tex>Involved \leftarrow \varnothing</tex>
'''for''' <tex>q \in C</tex> '''and''' <tex>r \in Inv[q][a]</tex>
<tex>i = Class[q]</tex>
'''if''' <tex>Size[i] == 0</tex>
'''insert''' <tex>i</tex> '''in''' <tex>Involved</tex>
<tex>Size[i]++</tex>
'''for''' <tex>q \in C</tex> '''and''' <tex>r \in Inv[q][a]</tex>
<tex>i = Class[q]</tex>
'''if''' <tex>Size[i] < Card[i]</tex>
'''if''' <tex>Twin[i] == 0</tex>
<tex>Counter++</tex>
<tex>Twin[i] = Counter</tex>
'''move''' <tex>r</tex> '''from''' <tex>i</tex> '''to''' <tex>Twin[i]</tex>
'''for''' <tex> j \in Involved</tex>
<tex>Size[j] = 0</tex>
<tex>Twin[j] = 0</tex>
Для быстрой проверки, находится ли пара <tex>(C,a)</tex> в очереди <tex>S</tex>, будем использовать массив <tex>InQueue</tex> размера <tex>|Q| \times |\Sigma|</tex>, где <tex>InQueue[C][a] = true</tex>, если пара <tex>(C,a)</tex> содержится в очереди.
