HDU 6153 A Secret KMP计数

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

给定两个串$s_1$,$s_2$,求$s_2$的每一个后缀在$s_1$中出现的次数$\times$长度的和。

将$s_1$,$s_2$进行反转,就变成了求$s_2$的每一个前缀在$s_1$中出现的次数$\times$长度的和。处理出$s_2$的next数组,用$s_2$对$s_1$进行匹配,假设$s_2[j]$和$s_1[i]$匹配上了,那么新出现的前缀就有$s_2[j],s_2[next[j]],s_2[next[next[j]],……$。但是并不能在匹配的过程中进行next跳转计数,会超时的。可以记录每个匹配长度值出现的次数,那么如果前缀$j$出现过,那么前缀$next[j]$也一定出现过。匹配完后,cnt[next[j]] += cnt[j]即可算出每个前缀出现的次数。