【codechefTASTRMAT】String Matching

2014年12月28日1,1970

其实我没有参赛。。。在比赛时间被人拉去做了这一道。。。

你们就坑我吧

设L=n-m

对于B的第1个字符,其匹配的是A的一个区间1到1+L

若其与A[1]不同,则hash值增加100001^m

与A[1+K]不同,则hash值增加100001^(n-K)

用数据结构支持查询1到1+L对hash值的贡献

即第K位与B的第1个字符不同则hash值增加100001^(n-K),相同增加0

用个线段树or树状数组(实际上前缀和就行)

接着考虑

对于B的第2个字符,其匹配的是A的一个区间2到2+L

若其与A[2]不同,则hash值增加100001^n

与A[2+K]不同,则hash值增加100001^(n-K)

……

我们发现,线段树每个位置的hash值每次应除以100001

于是,我们预处理100001^K在mod 1000000007意义下的逆元

唉我用个暴力找出100001^K的逆元是943660570^K(真是逗。。。)

对于B的第i个字符,将hash值乘上100001^(m-i+1)的逆元,最后累加hash值即可