求对于\(B\)的每一个位置 \(i\)，从这个位置开始连续\(m\)个字符形成的子串是否可能与\(A\)串完全匹配.\(1\le m\le n \le 3*{10}^5\)

两个位置\(A_i\)与\(B_{j+i}\)匹配有三种情况：

1. \(A_i\)为'*'
2. \(B_{i+j}\)为'*'
3. \(A_i = B_{i+j}\)，即\(A_i-B_{i+j}=0\)

那么显然可以令'*'所在位置为0，把三种情况乘起来就可以判断一个位置是否匹配了

判断从\(j\)开始的\(m\)个位置是否匹配就是\[S(j)=\sum_{i=1}^m(A_i-B_{i+j})^2*A_i*B_{i+j}\]

\[S(j)=\sum_{i=1}^m(A_i^2-2*A_i*B_{i+j}+B_{i+j}^2)*A_i*B_{i+j}\]

\[=\sum_{i=1}^mA_i^3*B_{i+j}-2\sum_{i=1}^mA_i^2*B_{i+j}^2+\sum_{i=1}^mA_i*B_{i+j}^3\]

把\(A\)翻转求卷积就好了

vector
    
      q;double eps=1e-6;int dcmp(double x){if(fabs(x) < eps) return 0; return 1;}char c[Maxn];void solve(){    m=read(), n=read(); scanf("%s", c+1);    for(int i=1; i <= m; i++) f[1][m-i].a=c[i] == '*' ? 0 : c[i]-'a'+1,        f[2][m-i].a=f[1][m-i].a*f[1][m-i].a, f[3][m-i].a=f[1][m-i].a*f[2][m-i].a;    scanf("%s", c);    for(int i=0; i < n; i++) g[1][i].a=c[i] == '*' ? 0 : c[i]-'a'+1,        g[2][i].a=g[1][i].a*g[1][i].a, g[3][i].a=g[1][i].a*g[2][i].a;    while(lim <= n+m-2) lim<<=1, l++;    for(int i=0; i < lim; i++) r[i]=(r[i>>1]>>1)|((i&1)<