主要都是用来解决有“通配符”、“模糊匹配”等的问题（如果没有这些东西直接kmp多好）。并且这些题目中，“通配符”能够代表的字符数量是一定的，否则就没有办法卷积了。
字符集较小：对每个字符单独考虑是否匹配
CF528D Fuzzy Search
有两个只包含$A,C,G,T$的字符串$S$和$T$，长度分别为$n,m$。给定一个限制宽度$K$。定义字符串$T$在$S$的$i$位置上匹配，当且仅当：$\forall j\in [1,m],\exists p\in [max((i+j-1)-K,1),min((i+j-1)+K,n)]$，使得$S[p]=T[j]$。问$T$在哪些位置上匹配。$1\le m\le n\le 200000,K\le 200000$。
Solution：可以考虑单独计算$match(i,c)$，表示$[i,i+m-1]$这个子串与$T$中的字符$c$的匹配数量。那么一个位置匹配的条件是$\sum match(i,c) =m$。
我们先枚举字符。那么我们设$f(i)=[S[i-K,i+K]中存在字符c]$，$g(i) = [T[i]=c] $。那么我们需要求的就是$h(i)=\sum_{j=1}^m g(j)\times f(i+j-1)$。把$g$翻一下用FFT算即可。
bzoj 3160 万径人踪灭
在一个只包含$a,b$的字符串中选取一个子序列，使得：
1.位置和字符都关于某条对称轴对称对称。
2.不能是连续的一段。
问方案数对$1000000007$取模的值。
Solution：等价于“位置和字符都对称的子序列数量”减去“连续的回文子串数量”，后者可以用manacher求出。
对于前者，我们考虑计算每个对称轴的贡献。假设有$x$个字符关于这个对称轴对称，那么这个对称轴的贡献就是$2^x-1$。两个位置关于$mid$对称等价于两个位置下标的和等于$mid\times 2$。我们枚举$mid\times 2$，分开计算两种字符各有多少个位置关于它对称。加入当前枚举的是$c$，设$f(x)=\sum_{i=1}^n [S_i=c]x^i$，那么我们要求的就是这个函数的平方。
注意，在卷积中，两个不同的位置$i,j$对$i+j$的贡献会被计算两次（第一个多项式选$i$，第二个多项式选$j$和第一个多项式选$j$，第二个多项式选$i$），而两个相同位置的贡献只会被算一次。
字符集较大：玄学构造比较函数
bzoj4259 残缺的字符串
有两个仅包含小写字母和的字符串$A$和$B$，其中 作为通配符，可以匹配任意一个字符。问$A$在$B$的哪些位置出现过。$1\le |A|\le |B| \le 300000$
Solution：
假设$|A|=m,|B|=n$。
如果我们定义一个函数$f(x,y)=A[x]-B[y]$，那么这个函数在$A[x]=B[y]$的时候就会返回$0$，否则就不会返回$0$。我们似乎可以通过判断$\sum_{i=1}^m A[i]-B[p+i-1]$是否为$0$来判断$p$这个位置是否可以与$A$匹配。但是这样是错误的，因为$f$的返回值有正有负，可能会出现正负数互相抵消的情况。
那么经过前人无数挣扎发现可以定义$f(x,y)=(A[x]-B[y])^2$作为比较函数。这样有两个好处：
1.$(A[x]-B[y])^2=A[x]^2+B[y]^2-2A[x]B[y]$，这个东西用FFT优化，可以在$n\log n$的时间内求出所有的$\sum_{i=1}^m (A[i]-B[p+i-1])^2$。
2.函数值均为非负数。因此如果有一个位置的函数值不为$0$，那么求和的结果就不为$0$。
现在考虑怎么做这道题：构造一个函数，当$A[x]=B[y]$或者$A[x],B[y]$中有一个为 * 的时候，$f(x,y)$为$0$；否则为一个正数。
如果令 * 的值为$0$，其他字符$c$的值为$c-‘a’+1$，那么构造$f(x,y)=(A[x]-B[y])^2 A[x]B[y]$恰好可以满足这个条件。
考虑怎么优化：
这玩意也可以用FFT优化，做三次卷积就可以了，只是常数略大QAQ。