hdu 4436 | 2012 Asia Tianjin Regional Contest str2int (dp+后缀自动机,多串建立)

http://acm.hdu.edu.cn/showproblem.php?pid=4436

题意:

给出n个仅由数字组成的字符串,问n个字符串的所有不同子串的和。

思路:

SAM水题

从初始状态开始,走过所有路径,就是该SAM表示的所有的(不重复)子串。

因此只需要从根节点按照拓扑序(这回是根据len从小到大)转移好了。

考虑num[i]表示从SAM中的init状态到i状态能表示的子串的数量。

dp[i]表示从SAM中的init状态到i状态所表示的子串对应的和(也就是到该节点的子串的答案)

那么对于SAM中一个u->v(其中u和v是状态,设转移边为j,j属于0..9)的转移

num[v]+=num[u]

dp[v] = dp[u] * 10 + num[u] * j

初始根节点num[rt]=1,表示唯一的空串。

需要注意,前缀0的数不考虑,所以SAM中 init状态不转移0这条边。

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz