小科技之卷积解决字符串匹配问题
OI中有各种字符串匹配问题，常见的有单模式串匹配、多模式串匹配和子串匹配等，一般可以用KMP、AC自动机、SAM解决。如果涉及到其他形式的单模式串匹配，这些传统的方式很不好解决，有没有更灵活的处理方法或者通法呢？
答案是有的，而且就是耳熟能详的FFT/NTT。
我们先考虑最基础的单模式串匹配，求长为m的字符串T在长为n的字符串S里出现了多少次，只不过我们要用卷积来实现。具体的，我们设\(C(i,j)\)表示\((s_i-t_j)\)，即这两位是否相等，相等就为0，如果匹配了，那么自然有\(\sum\limits_{i=0}^{m-1}C(x-m+i+1,i)=0\)，但是这样有反例，例如\(ab\)和\(ba\)都可以和\(ab\)匹配，因此我们改成\(\sum\limits_{i=0}^{m-1}\left|C(x-m+i+1,i)\right|=0\)才行。但是我们维护这个也是\(O(m)\)的，所以我们考虑给这一项平方，再设\(ans(x)=\sum\limits_{i=0}^{m-1}C(x-m+i+1,i)^2=\sum\limits_{i=0}^{m-1}(s_{x-m+i+1}-t_{i})^2\)，我们暴力拆柿子，得：
\[ans(x)=\sum\limits_{i=0}^{m-1}s^2_{x-m+i+1}-2\times s_{x-m+i+1}\times t_{i}+t^2_{i}=\sum\limits_{i=0}^{m-1}s^2_{x-m+i+1}+\sum\limits_{i=1}^m t^2_i-\sum\limits_{i=0}^{m-1}2\times s_{x-m+i+1}\times t_i \]这时前两项可以预处理后\(O(1)\)算，问题就在于怎么求最后一项。我们发现这个形式不好看，于是我们把T翻转，即\(t_i\)变成\(t_{m-i-1}\)，那么就变成了
\[\sum\limits_{i=0}^{m-1}2\times s_{x-m+i+1}\times t_{m-i-1} \]注意到\(x-m+i+1+m-i-1=x\)，那么这显然就是一个卷积式，我们可以\(O(n\log n)\)求出每一项，这样就可以\(O(n\log n)\)求出\(ans(x)\)了。
从这个算法得到启发，我们来总结做题的方法。
第一步：设计通配函数，即上文中的\(C(i,j)\)。
第二步：设计完全通配函数，即上文中的\(ans(x)\)。
第三步：计算每一位的完全通配函数的值。
来看几道简单的例题叭
标签：匹配,limits,卷积,sum,times,字符串 From： https://www.cnblogs.com/Xttttr/p/17207151.html