[HDU6153]A Secret(KMP)

发布于 2018-02-20  110 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU6153]A Secret(KMP)

Description

Today is the birthday of SF,so VS gives two strings S1,S2 to SF as a present,which have a big secret.SF is interested in this secret and ask VS how to get it.There are the things that VS tell:
Suffix(S2,i) = S2[i...len].Ni is the times that Suffix(S2,i) occurs in S1 and Li is the length of Suffix(S2,i).Then the secret is the sum of the product of Ni and Li.
Now SF wants you to help him find the secret.The answer may be very large, so the answer should mod 1000000007.

Http

HDU

Tag

KMP

题目大意

给出两个串,求第二个串的每一个后缀在第一个串中出现的次数。

解决思路

首先把两个串都翻过来变成处理前缀,因为\(KMP\)就是处理前缀的嘛。
首先考虑一个稍微暴力一点的办法,那就是对于每一个\(B\)串的前缀,我们都与\(A\)串作一次匹配。这样的复杂度是\(O(n^2)\)。
复杂度为什么会这么高呢?考虑我们算了哪些重复的东西,比如若前缀\(abbcdefg\)在\(A\)串中出现了,那么\(a,ab,abc,abcd,abcde,abcdef\)这些都出现了,而且我们每个都算了一遍。
怎么去掉这些重复计算的呢?我们把每一个前缀出现的次数拆开,转化成算\(A\)串中的某一个位置对于\(B\)串的哪些位置有贡献,有多少贡献。
但这样还是不好算,这时借助\(KMP\)中\(Next\)的性质,即\(Next[i]\)表示以\(i\)结尾的后缀的最长相同前缀后缀,那么一定就有若\(A\)串中的位置\(pos\)能匹配\(B\)串以\(i\)结尾的前缀,那一定也能匹配以\(Next[i]\)结尾的前缀,依次类推,也能匹配\(Next[Next[i]]\),\(Next[Next[Next[i]]]\),……
所以我们只要求出\(A\)串的每一个位置对哪个\(B\)串的最长前缀有贡献。注意这里是对B串求Next然后在B串中匹配A串。求完之后,再倒过来循环把上面包含关系的贡献加上,具体来说就是记\(Cnt[i]\)表示前缀\(i\)出现的次数,那么倒着循环\(i\),\(Cnt[Next[i]]+=Cnt[i]\)。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU6153]A Secret(KMP)


HNCJ OIer