Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:雁过留声——用AC自动机的状态dp

Posted by Troy_Cornelius at 2011-05-22 03:09:29 on Problem 3691
In Reply To:雁过留声——用AC自动机的状态dp Posted by:fanhqme at 2009-07-18 22:04:49
> 终于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了,自我庆祝一下...竟然把帖子写得如此之长

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator