F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:祝各位Oier新年快乐,Rp++!
大视野在线测评-欢迎您
[ New Thread ]
Problem 4503 >> 求此题做法。。。
xuruifan @ 2016-04-08 08:35:21
[ Quote ] [ Edit ] [ Delete ] 1#
RT
CreationAugust @ 2016-04-08 08:44:30
[ Quote ] [ Edit ] [ Delete ] 2#
可以使用FFT
详情请看之前的一道题 残缺的字符串
lavendir @ 2016-04-08 10:28:17
[ Quote ] [ Edit ] [ Delete ] 3#
我们将T翻转,并令c[j + m - 1] = sigma((a[j + i] - b[m - 1 -i]) ^ 2 * a[j + i] * b[m - 1 - i]) (0 <= i < m)
其中m为T的长度,a[i]表示S的第i个字符的(a视为1,b视为2,依次类推),b[i]为T的第i个字符,当T[i] = '?'时,令b[i] = 0.
可以发现,c[j + m - 1] = 0当且仅当S从第j个位置开始可以匹配上T。于是计算出所有的c即可
注意到上式实际上是一个卷积,于是使用快速傅立叶变换(FFT)求解即可,时间复杂度O(nlgn)
xuruifan @ 2016-04-08 10:51:37
[ Quote ] [ Edit ] [ Delete ] 4#
但是100ms内是怎么做到的?乱搞+数据弱?
lixuanjing @ 2017-12-11 13:48:39
[ Quote ] [ Edit ] [ Delete ] 5#
可否用kmp求解
nzhtl1477 @ 2017-12-11 13:48:59
[ Quote ] [ Edit ] [ Delete ] 6#
VK45.03
[Top] [Previous Page] [Next Page]

HOME Back