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

【题目大意】

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

【算法分析】

嗯,我又在刷水题。。。

就是建一个AC自动机(DFA)。

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

转移就是用自动机啦。

【其它】

1Y

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

【CODE】

#include

加入对话

5条评论

留下评论

回复 Legend_Ni 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注