Hopcraft 算法——DP 套 DP 的无用利器
前言
论文下载链接
《浅谈有限状态自动机及其应用》徐哲安
链接2
建议自己放到 markdown 看文字。
带你快速入门。
Part.1 定义
确定性有限状态自动机（DFA）：是一个五元组
语言：是字符集上
-
假设
M=m_0m_1...m_n ，其中m 为单个字符 -
存在一个起始节点
s ，满足从这个节点x 开始走，每次接受m_i ，即走向\delta(x,m_i) 。 -
如果最终停在一个接受状态，则称这个自动机接受语言
M ，否则不接受。
正则语言：即存在一个自动机，使得
我一般简记正则表达式等于正则语言。
Part.2 DFA 的最小化
一般的自动机只存在一个接受状态，但我们为了方便应用，扩展这这个自动机存在多个接受状态，且同一个接受状态内部不区分，不同接受状态和不能被接受的状态相互区分。
（下文称节点拥有的接受状态的类别或者不能被接受直接称为状态）
如果我只关心这个问题：
- 给定一些字符串，问这些字符串最后所处的节点的状态是什么
由于这些字符串有很多，那么我希望缩减 DFA 的规模来做到快速处理。
具体的，若两个节点
-
若等价类
A 有边连向 等价类B ，那么A 内部的任何一个点都有边连向等价类B 。 -
任何一个等价类的所有节点的状态相同（接受空串即可）
那么我们考虑构造一个新 DFA，满足有这些等价类作为节点，边按照原来 DFA 的相对关系连边。显然这两个 DFA 是等价的。
显然新的 DFA 是一个最小 DFA，且是唯一的最小 DFA（证明见论文）。
考虑使用 Hopcraft 算法来求出一个 DFA 的最小 DFA。大体思想如下：
-
我们初始将 DFA 节点按照所属的状态分成一些等价类。
-
我们遍历所有等价类：对于每个等价类
X ，按字符集依次考虑每个连向他等价类Y ，若Y 里面的所有点不都连向X ，显然连边的和不连边的不属于一个等价类。那么我们把Y 裂成两个等价类。 -
重复上述过程，若一轮过后没有等价类分裂，那么其就是最小 DFA：证明见论文的 4.1，大概就是考虑设
\delta^k 表示满足这个条件的等价类：所有小于等于k 的串在这个等价类中的状态都相同。考虑从\delta^k \to \delta^{k+1} ，发现等价类不变，因此可以推到\delta^{\inf} ，即上文根据定义划分的最小 DFA。
考虑优化上述过程，我们维护一个集合
-
每次从
W 中取出一个集合X 并从W 中删除 -
找到所有有向
X 连边的等价类Y ，若能划分，把其分成两部分A 和B 。若Y 没有被W 考虑过，则把A 和B 都放进W ；否则把大小较小的那个放进W 里。
唯一的问题是为什么不需要把
再考虑一下时间复杂度：
-
一方面需要遍历每个放进
W 的集合X -
另一方面，在
Y 被分裂时，若Y 被考虑过，那么只会把较小的那一个塞进W ，此时对于较小的集合内的点来说，再被W 遍历到的时候所在的等价类大小至少/2 ；否则贡献在前一步算过了（因为塞进去的集合是还没有被考虑过的）
因此复杂度为
代码：
int bel[N],nxt[N][11],ch[N][11],sz[N];
//bel[0] -> 1 起始状态
//bel[i] -> 2 ~ 11 接受状态
//siz 当前 eq 的大小（因为会延迟更新 eq）
map<i128,int>mp;
vector<int>pre[N][10],eq[N],ele[N];//反边 ; 等价类 ; 当前被区分的等价类
void rebuild(int x){vector<int>tmp;for(auto y:eq[x])if(bel[y]==x)tmp.push_back(y);eq[x].swap(tmp);}
//考虑延迟删除 eq[x] 内不符合的点，只动态更新当前 eq 的大小
bool check(int x){int t=0;for(auto y:eq[x])if(bel[y]==x)t++;return t==sz[x];}
void Hopcraft()
{
queue<int>q;cnt=11;
for(int i=1;i<=tot;i++)eq[bel[i]].push_back(i),sz[bel[i]]++;
for(int i=1;i<=tot;i++)for(int c=0;c<=9;c++)pre[ch[i][c]][c].push_back(i);
for(int i=1;i<=11;i++)q.push(i);while(!q.empty())
{
int x=q.front();q.pop();
rebuild(x);for(int c=0;c<10;c++)//按边考虑
{
vector<int>p;for(auto y:eq[x])for(auto z:pre[y][c])//找出每一个可能被 x 划分的等价类 z
{
if(ele[bel[z]].empty())p.push_back(bel[z]);
ele[bel[z]].push_back(z);
}
for(auto y:p)if(ele[y].size()<sz[y])//能被划分
{
cnt++;for(auto z:ele[y])eq[cnt].push_back(z),bel[z]=cnt;
sz[cnt]=ele[y].size();sz[y]-=sz[cnt];
if(sz[cnt]*2>sz[y])//保证较大的在队列前，较小的在队列后
//那么如果此时 y 被遍历过，加入正好的是较小的数
//否则正好遍历两个集合
{
rebuild(y);for(auto z:eq[y])bel[z]=cnt;for(auto z:eq[cnt])bel[z]=y;
eq[y].swap(eq[cnt]);swap(sz[cnt],sz[y]);
//暴力遍历 y 是没有关系的，此时保证 \sum y <= x*2，可以看做遍历 x 的复杂度乘上常数
}
q.push(cnt);
}
for(auto y:p)ele[y].clear();
}
}
for(int i=1;i<=cnt;i++)rebuild(i);
}Part.3 例题
一般题目中是没有给出接受状态的，那么我们可以考虑把所有合法状态分成几个接受状态类。如 CF924F。此时的判断依据是在自动机终止状态时是否存在一个差小于等于
代码：
#include<bits/stdc++.h>
#define int long long
#define i128 __int128
using namespace std;
const int N=2e4+100,M=800;
int tot=0,cnt=0;
i128 vt[N],U;
int bel[N],nxt[N][11],ch[N][11],sz[N];
//bel[0] -> 1 起始状态
//bel[i] -> 2 ~ 11 接受状态
//bel[i] -> 12 其他状态
//siz 当前 eq 的大小（因为会延迟更新 eq）
map<i128,int>mp;
vector<int>pre[N][10],eq[N],ele[N];//反边 ; 等价类 ; 当前被区分的等价类
void rebuild(int x){vector<int>tmp;for(auto y:eq[x])if(bel[y]==x)tmp.push_back(y);eq[x].swap(tmp);}
bool check(int x){int t=0;for(auto y:eq[x])if(bel[y]==x)t++;return t==sz[x];}
void Hopcraft()
{
queue<int>q;cnt=11;
for(int i=1;i<=tot;i++)eq[bel[i]].push_back(i),sz[bel[i]]++;
for(int i=1;i<=tot;i++)for(int c=0;c<=9;c++)pre[ch[i][c]][c].push_back(i);
for(int i=1;i<=11;i++)q.push(i);while(!q.empty())
{
int x=q.front();q.pop();
rebuild(x);for(int c=0;c<10;c++)//按边考虑
{
vector<int>p;for(auto y:eq[x])for(auto z:pre[y][c])//找出每一个可能被 x 划分的等价类 z
{
if(ele[bel[z]].empty())p.push_back(bel[z]);
ele[bel[z]].push_back(z);
}
for(auto y:p)if(ele[y].size()<sz[y])//能被划分
{
cnt++;for(auto z:ele[y])eq[cnt].push_back(z),bel[z]=cnt;
sz[cnt]=ele[y].size();sz[y]-=sz[cnt];
if(sz[cnt]*2>sz[y])//保证较大的在队列前，较小的在队列后
{
rebuild(y);for(auto z:eq[y])bel[z]=cnt;for(auto z:eq[cnt])bel[z]=y;
eq[y].swap(eq[cnt]);swap(sz[cnt],sz[y]);
}
q.push(cnt);
}
for(auto y:p)ele[y].clear();
}
}
for(int i=1;i<=cnt;i++)rebuild(i);
for(int i=1;i<=cnt;i++)for(int j=0;j<=9;j++)nxt[i][j]=bel[ch[eq[i][0]][j]];
for(int i=1;i<=cnt;i++)for(int j=0;j<=9;j++)ch[i][j]=nxt[i][j];
// swap(nxt,ch);
}
i128 getnxt(i128 S,int c){auto T=((S>>c)|(S<<c));for(int i=0;i<=c;i++)if(S&(1<<i))T|=(1<<(c-i));T&=U;return T;}
int f[20][10][M];//f[i][j][S] 表示剩 i 位没有填，要求最终值 <=j，当前在状态 M 的方案数
int solve(int r,int k)
{
vector<int>vt;while(r)vt.push_back(r%10),r/=10;
int res=0,st=1;for(int i=vt.size()-1;i>=0;i--)
{
for(int j=0;j<vt[i];j++)res+=f[i][k][ch[st][j]];
st=ch[st][vt[i]];
}
return res+f[0][k][st];
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
vt[mp[1]=tot=1]=1;U=(__int128)1<<73;U--;
for(int i=1;i<=tot;i++)
{
for(int c=0;c<=9;c++){i128 g=getnxt(vt[i],c);if(!mp[g])vt[mp[g]=++tot]=g;ch[i][c]=mp[g];}
for(int p=0;p<=9;p++)if(vt[i]&(1<<p)){bel[i]=p+2;break;}
}bel[1]=1;
Hopcraft();
// cout<<tot<<endl;
for(int s=1;s<=cnt;s++)
{
int p;for(p=0;p<=9;p++)if(vt[eq[s][0]]&(1<<p))break;
for(int j=p;j<=9;j++)f[0][j][s]=1;
}
for(int i=1;i<20;i++)for(int j=0;j<=9;j++)for(int s=1;s<=cnt;s++)for(int c=0;c<=9;c++)
f[i][j][s]+=f[i-1][j][ch[s][c]];
int _;cin>>_;while(_--)
{
int l,r,k;cin>>l>>r>>k;
cout<<solve(r,k)-solve(l-1,k)<<endl;
}
return 0;
}Part.4
一般正解的 DFA 状态数都有保证。除非你是打暴力。所以对于 FSZ，WMH 来说就没有多大用。