Изменения
→Реализация
*<tex>\mathtt{R}</tex> {{---}} класс состояний ДКА.
'''function''' findEquivalenceClasses<tex>(Q,\ F,\ \delta)</tex>: '''pair<set, set>vector'''
<tex>\mathtt{P} \leftarrow \{ F, \ Q \setminus F \}</tex>
<tex>\mathtt{S} \leftarrow \varnothing </tex>
Понятно, что нам нет никакой необходимости просматривать все классы в разбиении. Вполне достаточно рассмотреть лишь те классы, из состояний которых есть хотя бы одно ребро в состояния сплиттера. Обозначим множество таких классов за <tex>T'</tex> (его нужно будет эффективно находить для каждой пары <tex>\langle C,\ a \rangle</tex>).
'''function''' findEquivalenceClasses<tex>\mathtt{findEquivalenceClasses}(Q,\ F,\ \delta)</tex>:'''vector'''
<tex>\mathtt{P} \leftarrow \{ F, \ Q \setminus F \}</tex>
<tex>\mathtt{S} \leftarrow \varnothing </tex>
'''for''' <tex>c \in \Sigma</tex>
'''while''' <tex>\mathtt{S} \ne \varnothing</tex>
<tex>\langle C,\ a \rangle</tex> <tex>\leftarrow</tex> '''pop''' '''from''' <tex>\mathtt{S}</tex>
<tex>\mathtt{Inverse} \leftarrow \{r \ | \ r \in Q, \ \delta(r, a) \in C\}</tex>
<tex>T' \leftarrow \{R \ | \ R \in \mathtt{P}, \ R \cap \mathtt{Inverse} \neq \varnothing\}</tex> <font color=darkgreen>// находим классы, из состояний которых есть ребро в состояния сплиттера </font> '''for''' <tex>R</tex> '''in''' <tex>T'</tex> <font color=darkgreen>// перебираем только классы входящие в <tex>T'</tex></font>
<tex> R_1, R_2 \leftarrow </tex> <tex>\mathtt{split}(R,\ C,\ a)</tex>
'''if''' <tex> R_1 \ne \varnothing </tex> '''and''' <tex> R_2 \ne \varnothing </tex>
'''if''' <tex>\langle R,\ c \rangle</tex> '''in''' <tex> \mathtt{S}</tex>
'''else'''
'''if''' <tex> |\mathtt{P}[R_1]| \leqslant |\mathtt{P}[R_2]| </tex>
'''else'''
'''return''' <tex>\mathtt{P}</tex>
*<tex>\mathtt{Twin}</tex> {{---}} массив, хранящий в <tex>\mathtt{Twin}[i]</tex> номер нового класса, образовавшегося при разбиении класса <tex>i</tex>,
'''function''' findEquivalenceClasses<tex>\mathtt{findEquivalenceClasses}(Q,\ F,\ \delta)</tex>:'''vector'''
<tex>\mathtt{P} \leftarrow \{ F, \ Q \setminus F \}</tex>
'''for''' <tex>c \in \Sigma</tex>
'''while''' <tex>\mathtt{Queue} \ne \varnothing</tex>
<tex>\langle C,\ a \rangle</tex> <tex>\leftarrow</tex> '''pop''' '''from''' <tex>\mathtt{Queue}</tex>
<tex>\mathtt{Involved} \leftarrow \varnothing</tex>
'''for''' <tex>q \in C</tex> '''and''' <tex>r \in \mathtt{Inv}[q][a]</tex>
<tex>i = \mathtt{Class}[r]</tex>
'''if''' <tex>\mathtt{Count}[i] == 0</tex>
<tex>\mathtt{Count}[i]++</tex>
'''for''' <tex> i \in \mathtt{Involved}</tex>
'''if''' <tex>\mathtt{Count}[i] < |\mathtt{P}[i]|</tex>
'''for''' <tex>q \in C</tex> '''and''' <tex>r \in \mathtt{Inv}[q][a]</tex>
<tex>i = \mathtt{Class}[r]</tex>
<tex>j = \mathtt{Twin}[i]</tex>
'''if''' <tex>j \neq 0</tex>
'''for''' <tex> i \in \mathtt{Involved}</tex>
<tex>j = \mathtt{Twin}[i]</tex>
'''if''' <tex> j \neq 0 </tex>
'''if''' <tex>|\mathtt{P}[j]| > |\mathtt{P}[i]|</tex> <font color=darkgreen>//Парный парный класс должен быть меньшего размера</font> <tex>\mathtt{swap}(\mathtt{P}[i],\ \mathtt{P}[j])</tex> <font color=darkgreen>//swap за <tex>\mathtt{O(1) }</tex> - просто переставить указатели</font> '''for''' <tex>r \in \mathtt{P}[j]</tex> <font color=darkgreen>//Обновляем обновляем номера классов для вершин, у которых они изменились</font>
<tex>\mathtt{Class}[r] = j</tex>
'''for''' <tex>c \in \Sigma</tex>
<tex>\mathtt{Count}[i] = 0</tex>
<tex>\mathtt{Twin}[i] = 0</tex>
Также стоит отметить, что собственно наличие/отсутствие пары в очереди можно не проверять. Если для некоторого <tex>c</tex> пара <tex>\langle i, c \rangle</tex> уже была в очереди, то мы добавим её "вторую половинку" <tex>\langle \mathtt{Twin}[i], c \rangle</tex>. Если её в очереди не было, то мы вольны сами выбирать, какой подкласс добавлять в очередь, и таким образом добавляем опять же <tex>\langle \mathtt{Twin}[i], c \rangle</tex>.
Кроме того, вместо очереди можно использовать вообще произвольную струтуруструктуру, хранящую элементы, в том числе стэк, множество, т.к. порядок извлечения нам по сути не важен.
===Время работы===
