[POJ3691 DNA repair]AC自动机、动态规划

【题目大意】

给定N个串，再给定一个主串，问将主串改为不含这个N个串为子串的串，至少需改动多少个字母？

【算法分析】

嗯，我又在刷水题。。。

就是建一个AC自动机（DFA）。

然后用F[i,j]表示已处理串长为i，然后在自动机中的状态j，至少要改动多少个字母。

转移就是用自动机啦。

【其它】

1Y

注意如果自动机中的next结点有终结标记，自己也应当标为终止。

【CODE】

#include