引入

给你两个字符串 。询问 是否匹配。其中 含有通配符 。 可以匹配任意一种字符。

分析

如果我们使用最常见的字符串匹配算法 我们发现，对于 的处理是非常复杂度的。这个我们引入一个函数 。叫做字符串 的距离函数。那么我们定义 。这样如果我们把 看做完全匹配的话，如果 我们就把他定义为 。这样就完美的解决了通配符的问题。但是由于引入了一个二元函数。我们计算上式子需要的时间复杂度为 。考虑函数展开 如果我们定义 这样我们得到了一个卷积形式。通过 或者 优化。总的复杂度变为 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1910000,P = 998244353;
int limit = 1,L = 0,r[N];
char S[N],T[N];
int A[N],B[N],C[N];
vector<int> Ans;
int ksm(int a,int b) {
    int x = 1;for(;b;b>>=1,a=1LL*a*a % P) {
        if(b & 1) x = 1LL * a * x % P;
    }return x;
}
void NTT(int *a,int type) {
    for(int i = 1;i < limit;i++) if(i > r[i]) swap(a[r[i]],a[i]);
    for(int mid = 1;mid < limit;mid <<= 1) {
        int wn = ksm(3,(P-1)/(mid<<1));
        for(int i = 0;i < limit;i += (mid << 1)) {
            for(int j = 0,w = 1;j < mid;j++,w = 1LL * w * wn % P) {
                int x = a[i + j],y = 1LL * w * a[i + j + mid] % P;
                a[i + j] = (x + y) % P;a[i + j + mid] = (x - y + P) % P;
            }
        }
    }
    if(type == -1) {
        reverse(a+1,a+limit);int inv = ksm(limit,P-2);
        for(int i = 0;i < limit;i++) a[i] = 1LL * a[i] * inv % P;
    }
}
void Init() {memset(B,0,sizeof(B));memset(C,0,sizeof(C));}
int main() {
    int n,m;
    scanf("%d%d%s%s",&n,&m,S+1,T+1);
    reverse(S+1,S+1+n);
    while(limit <= m + n) limit <<= 1,L++;
    for(int i = 0;i < limit;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));
    for(int i = 1;i <= n;i++) {
        if(S[i] != '*') C[i] = (S[i] - 'a' + 1) * (S[i] - 'a' + 1) * (S[i] - 'a' + 1);
        else C[i] = 0;
    }
    for(int i = 1;i <= m;i++) {
        if(T[i] != '*') B[i] = (T[i] - 'a' + 1);
        else B[i] = 0;
    }
    NTT(C,1);NTT(B,1);
    for(int i = 0;i < limit;i++) A[i] = (A[i] + (1LL * C[i] * B[i] % P)) % P;
    Init();
    for(int i = 1;i <= n;i++) {
        if(S[i] != '*') C[i] = (S[i] - 'a' + 1) * (S[i] - 'a' + 1);
        else C[i] = 0;        
    }
    for(int i = 1;i <= m;i++) {
        if(T[i] != '*') B[i] = (T[i] - 'a' + 1) * (T[i] - 'a' + 1);
        else B[i] = 0;        
    }
    NTT(C,1);NTT(B,1);
    for(int i = 0;i < limit;i++) A[i] = (A[i] - (2LL * C[i] * B[i] % P) + P) % P;
    Init();
    for(int i = 1;i <= n;i++) {
        if(S[i] != '*') C[i] = (S[i] - 'a' + 1);
        else C[i] = 0;        
    }
    for(int i = 1;i <= m;i++) {
        if(T[i] != '*') B[i] = (T[i] - 'a' + 1) * (T[i] - 'a' + 1) * (T[i] - 'a' + 1);
        else B[i] = 0;        
    }    
    NTT(C,1);NTT(B,1);
    for(int i = 0;i < limit;i++) A[i] = (A[i] + (1LL * C[i] * B[i] % P)) % P;
    NTT(A,-1);
    for(int i = n + 1;i <= m + 1;i++) {
        if(A[i] == 0) Ans.push_back(i - n);
//        cout << A[i] << endl;
    }
    printf("%d\n",Ans.size());
    for(auto p:Ans) printf("%d ",p);
    printf("\n");
    return 0;
}