FFT字符串匹配
本文半原创
参考资料：其实就是照抄的什么参考啊
我们知道KMP可以用来在线性复杂度内进行制胡窜匹配
今天教您一种新方法：用FFT进行字符串匹配
您可能觉得这很玄学，FFT不是做多项式卷积的吗，怎么还可以做制胡窜匹配
您先别着急，请接着听
我们设两个字符串--模式串(a)，长度为(m)，文本串(b)，长度为(n)。设下标为从0开始
定义函数(a(i))返回a串位置i的字符，(b(i))返回b串位置i的字符（其实就是下标）
定义匹配函数(c(x,y)=a(x)-b(y))，代表a串x位置和b串y位置是否匹配(也就是是否相同)
如果匹配，那么(c(x,y)=0)对吧
然后我们再定义完全匹配函数(displaystyle P(x)=sum_{i=0}^{m-1}c(i,x-m+i+1))，若(P(x)=0)，则称B以第(x)位结束的连续(m)位与A完全匹配
但是这个匹配函数是有问题的
他会导致字符串"ab"和字符串"ba"匹配，你想想是不是，一个-1一个1，加起来就是0喽
所以我们稍微改一下匹配函数：(c(x,y)=(a(x)-b(y))^2)，保证(c(x,y)ge 0)，这样是不是就没问题了啊
所以我们的(displaystyle P(x)=sum_{i=0}^{m-1}(a(i)-b(x-m+i+1))^2)
您还没有看出什么玄机来
我们可以把(a)串翻转，设翻转后的串为(s)，则满足(a(i)=s(m-i-1))对吧，下标是从0开始的
所以我们的(displaystyle P(x)=sum_{i=0}^{m-1}(s(m-i-1)-b(x-m+i+1))^2)
继续观察！发现什么了？？？要不我们换一下元，用(i)替换(m-i+1)，注意其中(i)的范围由([0,m-1])变换到了([0,m-1])你直接说没有变不就得了
所以我们的(displaystyle P(x)=sum_{i=0}^{m-1}(s(i)-b(x-i))^2)
要不我们把完全平方展开下
所以我们的(displaystyle P(x)=sum_{i=0}^{m-1}(s^2(i)-2s(i)b(x-i)+b^2(x-i)))
拆一下sigma
所以我们的(displaystyle P(x)=sum_{i=0}^{m-1}s^2(i)+sum_{i=0}^{m-1}b^2(x-i)-2sum_{i=0}^{m-1}s(i)b(x-i))
这式子是不是不错啊
第一项是个定值，可以直接算出啦
第二项，由于加的是一段区间，可以O(n)预处理前缀和
第三项！！！这是什么？不就是我们的卷积吗
FFT即可
时间复杂度O(nlogn)
诶对了
到了这里您可能会发现这个时间复杂度都没KMP优秀
您可能会问我这个算法有个吊毛用啊，FFT还没KMP好写(FFT其实也挺好写的)
别急听我接着讲
如果我们的字符串里有通配符呢
就是说这个通配符跟什么字符匹配都行（注意是字符而不是字符串）
您会发现KMP就GG了
然后我们继续考虑FFT做法
这次我们强制令通配符的ascii为0
定义我们的匹配函数(c(x,y)=(a(x)-b(y))^2a(x)b(y))，那么是不是对于有通配符的都能保证(c=0)了呢
然后就是推一波式子的事情了
大家可以试着推推
行了下面是结果
所以我们的(displaystyle P(x)=sum_{i=0}^{m-1}(s^3(i)b(x-i)-2s^2(i)b^2(x-i)+s(i)b^3(x-i)))
我们对(s,s^2,s^3,b,b^2,b^3)进行FFT，然后再DFT回来就行啦
有了这个算法之后不就是板子题啦
这题可以用SAM做，@顾z
好像还可以用哈希做。。。还是@顾z
温馨提示：根据生物学知识，人类DNA上的碱基只有四种
大家可以想一想正解
我们对ATCG贡献分开算，这里的贡献指的是不匹配的字符数
假设我们当前强行只计算模式串中A对于匹配串的贡献
先把模式串翻转一下
那么我们把模式串的A当做1，T C G都当做0，把文本串的A当做0，T C G都当做1
然后直接让模式串和文本串卷积（数字很小，可以用NTT优化卷积）
累加的贡献就是A与TCG不匹配的
最后把所有<=3的位置统计即为答案
总结：
这种带通配符/不匹配的字符串题我们一般是构造关于字符串的函数，对某个字符串翻转，然后进行卷积再各种处理。
这种题只是FFT的一种应用。