やったこと

DFA

DFA の最小化のアルゴリズムの際に partition refinement というデータ構造を使う。
これは n 個の要素の集合の細分の計算が、細分をする集合の大きさでできるもの。
つまり、{1, 2, 3 | 4, 5} に対して {2, 3, 4} で細分して {1 | 2, 3 | 4 | 5} を求めるのを |{2, 3, 4}| = 3 の計算量でできる。

この実装には双方向連結リストを使う場合と、可変な Set を使う場合があるのだけど、本質的にはその要素がどの部分に属しているのかを保持しておくことで実現される。

というかこれ日本語の情報ないが。