HDU 3247

AC自动机

先预处理所有可以作为合法单词结尾的点之间的距离，然后在这些点之间状态DP即可

[cpp]
#include
#include
#define INF 0x3f3f3f3f
#define MAXN 60005
char s[1002];
int n,m;
int next[MAXN][2],fail[MAXN],flag[MAXN],pos;
int newnode(){
next[pos][0]=next[pos][1]=0;
fail[pos]=flag[pos]=0;
return pos++;
}
void insert(char *s,int id){
int p=0;
for(int i=0;s[i];i++){
int k=s[i]-'0',&x=next[p][k];
p=x x:x=newnode();
}
if(id==-1)flag[p]=-1;
else flag[p]|=(1< }
int q[MAXN],front,rear;
void makenext(){
q[front=rear=0]=0,rear++;
while(front int u=q[front++];
for(int i=0;i<2;i++){
int v=next[u][i];
if(v==0)next[u][i]=next[fail[u]][i];
else q[rear++]=v;
if(v&&u){
fail[v]=next[fail[u]][i];
if(flag[fail[v]]==-1)flag[v]=-1;
else flag[v]|=flag[fail[v]];
}
}
}
}
#define MAXM 1025
int d[MAXN][MAXM],pnt[MAXM],ps,map[MAXM][MAXM],dis[MAXN];
inline int min(int x,int y){return x void bfs(int p){
for(int i=0;i q[front=rear=0]=pnt[p],rear++;
dis[pnt[p]]=0;
while(front int u=q[front++];
for(int i=0;i<2;i++){
int v=next[u][i];
if(flag[v]<0||dis[v]!=INF)continue;
dis[v]=dis[u]+1;
q[rear++]=v;
}
}
for(int i=0;i }
int dp(){
for(int i=0;i<(1< d[0][0]=0;
for(int i=0;i<(1< for(int u=0;u if(d[i][u]==INF)continue;
for(int v=0;v d[i|flag[pnt[v]]][v]=min(d[i|flag[pnt[v]]][v],d[i][u]+map[u][v]);
}
}
int ans=INF;
for(int i=0;i ans=min(ans,d[(1< return ans;
}
int main(){
while(scanf("%d%d",&n,&m),n||m){
pos=0;newnode();
for(int i=0;i scanf("%s",s);
insert(s,i);
}
for(int i=0;i scanf("%s",s);
insert(s,-1);
}
makenext();
ps=0;
for(int i=0;i if(i==0||flag[i]>0)pnt[ps++]=i;
for(int i=0;i bfs(i);
printf("%d\n",dp());
}
return 0;
}