终于AC了。用小号一共贡献了32个提交。
为了逐步删去debug、OJdebug(就是用制造OLE和TLE来判断程序的哪里是出问题的）
以及冗余代码，连着用小号ac了6次（不知情者还以为我高兴过头了）
不停地调试，最终还是通过比对
http://www.cnblogs.com/woodfish1988/archive/2008/11/19/1303492.html
给的程序过的。感谢这种助人为乐贴代码的人！
贴代码不是为了炫耀，也不是为了满足某些Ctrl+A+Crtl+C+Crtl+V+Alt+S的人，
而是真真正正的帮助苦苦调试却走投无路的勇敢者。

说说算法吧。如果吧20改成10，ATGC改成01串，那么是一个很裸的状态dp。
记录dp(i,j),为前i位，最近9个数字的状态是j的最小改动。
j用2进制压缩。不过照搬到这题上，状态数猛增到4得20次方，就是274877906944，不可能过。
不过，发现其实有些状态是一回事。
例如：
2
ATT
AA
?????
则GC,GG,AG,GA等等的状态都是一样的。
这使人联想到了AC自动机！
是的，其实实质不同的状态就是匹配时运行到的不同的自动机的状态。

于是，算法出炉了。dp(i,j)表示前i位，匹配程度到达j的最小改动数。
最多状态数不会超过1000（大致估计，其实会更少）。

AC自动机我写的时候发现了几个比较容易脑残的地方，提醒一下：
1.计算“失败”（或“后缀”）指针的时候，必须用bfs!
2.如果一个串的某个字串是危险的，那么他也是危险的。具体看下组数据：
2
ATGCAT
GC
ATGCAC
直接输出0的人赶快调吧

终于ac了，自我庆祝一下...竟然把帖子写得如此之长

• Re:雁过留声——用AC自动机的状态dp (114) HASK 2009-08-12 20:08:16
• Re:雁过留声——用AC自动机的状态dp (91) conanhjj 2009-10-03 05:02:54
• Re:哥们NB啊，雁过留声 我看见好多次了 (0) schindlerlee 2009-10-03 10:16:47
• Re:zan!! (835) blackdog 2009-10-04 00:11:27
• Re:雁过留声——用AC自动机的状态dp (835) Troy_Cornelius 2011-05-22 03:09:29
• Re:状态不会超过980 (9) chiya 2012-04-17 20:05:15
• Re:雁过留声——用AC自动机的状态dp (835) tcet030840zxp 2012-05-15 00:21:14
  • Re:雁过留声——用AC自动机的状态dp (9) tcet030840zxp 2012-05-15 00:21:46
• Re:顶范神！表示我居然1Y了，还是区域赛题，接下来2个月加油了~ (0) yuanchuanshun 2012-07-11 22:49:29