主题

主题

 
   

4503: 两个串

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=4503

Description

兔子们在玩两个串的游戏。给定两个字符串S和T,兔子们想知道T在S中出现了几次,

分别在哪些位置出现。注意T中可能有“?”字符,这个字符可以匹配任何字符。

Input

两行两个字符串,分别代表S和T

Output

第一行一个正整数k,表示T在S中出现了几次

接下来k行正整数,分别代表T每次在S中出现的开始位置。按照从小到大的顺序输出,S下标从0开始。

Sample Input

bbabaababaaaaabaaaaaaaabaaabbbabaaabbabaabbbbabbbbbbabbaabbbababababbbbbbaaabaaabbbbbaabbbaabbbbabab

a?aba?abba

Sample Output

0

HINT

S 长度不超过 10^5, T 长度不会超过 S。 S 中只包含小写字母, T中只包含小写字母和“?”


个人解法:

样例这么长结果给了一个答案0……终于做出了一道字符串题。这几天要么被卡精度要么被卡Hash反正就是过不去……

这题还是一个套路题……

定义两个字符串的距离是


a与b是等长的字符串。且当b[i]为通配符的时候,b[i]=0。

可以看出,两个字符串可以匹配,当且仅当两个字符串你的距离为0。

拆开这一部分:


根据FFT的套路,我们把B串翻转。

然后就变为了卷积。

注意b[i]^3在卷积中是多项式(1,1,1...1)*(b[1]^3,b[2]^3...b[len]^3)。这个卷积实质上是前缀和(本来也就是前缀和)。

可以把3次DFT的点值表达式合并起来,再做一次逆DFT。


细节问题:

以前习惯拿一个int数组来储存系数,后来改掉之后,误以为也是int数组,然而这时实数,所以系数判断是否为0应该是C[i].x<0.5。


代码如下:

https://code.csdn.net/snippets/2256623

 
 
评论