SPOJ_704
这个题目可以用AC自动机（其实应该说是trie图）+dp去做。
我们可以把问题等效成从X这个字符串里面挑出一些字符组成一个新的字符串，并且新的字符串中不能包含Y。我们可以把生成字符串的过程模拟成在trie图上行走的过程，则第i步时就会有两种选择，要么走到X[i]这个字符上，要么停留在原地，其中停留在原地就相当于把X[i]这个字符删掉了，因此代价应该增加1。为了保留第i步走到第j个点时的最小代价，可以用f[i][j]记录，当然空间可以优化成一维的。
最后我们把行走了len[X]步后的到达各个节点的最小代价统计一下，输出最小值即可。
#include<stdio.h>
#include<string.h>
#define MAXX 10010
#define MAXD 1010
#define INF 0x3f3f3f3f
int node, next[MAXD][128], safe[MAXD], q[MAXD], P[MAXD], wa[MAXD], wb[MAXD], *f, *g;
char bx[MAXX], by[MAXD];
void newnode(int cur, int k)
{
++ node;
safe[node] = 1;
memset(next[node], 0, sizeof(next[node]));
next[cur][k] = node;
}
void build()
{
int i, j, k, cur, front, rear;
front = rear = 0;
safe[0] = 1, P[0] = 0;
q[rear ++] = 0;
while(front < rear)
{
cur = q[front ++];
for(i = 0; i < 128; i ++)
{
if(k = next[cur][i])
{
q[rear ++] = k;
if(cur == 0)
P[k] = 0;
else
P[k] = next[P[cur]][i];
if(!safe[P[k]])
safe[k] = 0;
}
else
next[cur][i] = next[P[cur]][i];
}
}
}
void init()
{
int i, j, k, cur;
cur = node = 0;
memset(next[0], 0, sizeof(next[0]));
for(i = 0; by[i]; i ++)
{
k = by[i];
if(!next[cur][k])
newnode(cur, k);
cur = next[cur][k];
}
safe[cur] = 0;
build();
}
void solve()
{
int i, j, k, ans = INF, *t;
f = wa, g = wb;
memset(f, 0x3f, sizeof(f[0]) * node);
f[0] = 0;
for(i = 0; bx[i]; i ++)
{
memset(g, 0x3f, sizeof(g[0]) * node);
for(j = 0; j < node; j ++)
{
if(f[j] + 1 < g[j])
g[j] = f[j] + 1;
if(safe[k = next[j][bx[i]]] && f[j] < g[k])
g[k] = f[j];
}
t = f, f = g, g = t;
}
for(i = 0; i < node; i ++)
if(f[i] < ans)
ans = f[i];
printf("%d\n", ans);
}
int main()
{
while(scanf("%s%s", bx, by) == 2)
{
init();
solve();
}
return 0;
}