Luogu4173 残缺的字符串

Description

给定长度为 n 的字符串 A 和长度为 m 的字符串 B 。当以 A 为模式串时，你希望求出对于 B 的每一个位置 i ，从该位置开始的连续 n 个字符形成的子串是否能与 A 完全匹配。A B 中可能含有通配符 @ 。通配符可以视作为任意小写字母。
$1\leq n\leq m\leq 3\times 10^5$

Solution

《字符串哲学中的多项式方法》
多项式方法在字符串匹配问题中的应用也很广泛。
比较常见的一种类型是将字符映射成特定的值，使得卷积后数组位置上的值有特殊的含义。这种方法很灵活。
在本题中，我们先随机给字符（除通配符外）映射成一个值，将 A 中的字母映射成该值，B 中的字母映射成该值的逆元。那么，当没有通配符时，我们需要求解这样一个数组：

$f_i=\sum_{j=0}^{m}{A_j\times B_{i+j}}$

当 $f_i=m$ 时，意味着 i 位置是可行的。
观察到 $f_i$ 的求解是减法逆元的形式。我们令 $C_i=A_{m-1-i}$ ，则：

$f_i=\sum_{j=0}^{m}{A_{m-1-j}\times B_{i+j}}=\sum_{j+k=m-1+i}A_j\times B_k$

NTT 可以做。
通配符一定可以匹配上，所以我们并不需要通配符与其对应位参与该运算中，而可以在事后统计。于是我们将通配符映射为 0 ，并在 $f_i$ 处加上 $[1,i+m-1]$ 中通配符的数量 。
但是有可能恰好两个通配符匹配上了，此时理应只算一次贡献。这部分的容斥显然可以通过仅将通配符设为 1 后卷积得到，方法与上述求解 $f_i$ 类似，不再赘述。

另外一种方法是构造新运算。定义 $m(x,y)$ 表示 $A_x,B_y$ 是否匹配，若匹配则 $m(x,y)=0$ ；否则 $m(x,y)\ne 0$ 。
考虑到我们是这样判定两个子串是否相等的：

$[\sum_{i=0}^{n}m(i,i)=0]$

故我们需要该运算的结果满足非负性/非正性（防止抵消），并且可以兼容通配符。
其实从非负性/非正性就可以大致得出来了，我们可以如下构造 $m()$ 运算：

$m(x,y)=A_xB_y(A_x-B_y)^2$

并将通配符定义为 0 。
于是我们需要求的

$g_i=\sum_{j=0}^{n}m(i,i+j)$

也可以通过暴力展开括号后减法卷积求得。最后的结果为（设 $C_i=A_{m-1-i}$）：

$g_i=\sum_{j+k=i}C_j^3A_k+\sum_{j+k=i}C_j^2A_k^2+\sum_{j+k=i}C_jA_k^3$

代码采用的是第一种方法。

Code

int main(){

    scanf("%d%d",&m,&n);
    scanf("%s",t);scanf("%s",s);

    srand(19260817);
    for(int i=0;i<26;++i)
        d[i]=max(rand()%Mod,2),invd[i]=Q(d[i],Mod-2); // 注意随机化的值不能为 0
    
    for(int i=0;i<m;++i) f[i]=t[i]=='*';
    for(int i=0;i<n;++i) g[i]=s[i]=='*';
    reverse(f,f+m);
    Getmul(f,g,h,m,n);

    int sum=0;
    szs[0]=s[0]=='*';
    for(int i=1;i<n;++i) 
        szs[i]=szs[i-1]+(s[i]=='*');
    for(int i=0;i<m;++i) sum+=t[i]=='*';
    for(int i=0;i<m;++i) f[i]=t[i]=='*'?0:d[t[i]-'a'];
    for(int i=0;i<n;++i) g[i]=s[i]=='*'?0:invd[s[i]-'a'];
    reverse(f,f+m);
    Getmul(f,g,l,m,n);

    for(int i=0;i<=n-m;++i)
        if(l[i+m-1]-h[i+m-1]+sum+szs[i+m-1]-(i==0?0:szs[i-1])==m) 
            ans.push_back(i+1);
    printf("%d\n",ans.size());
    for(auto x:ans)
        printf("%d ",x);
    return 0;
}