HDU - 6975 Forgiving Matching

传送门：HDU - 6975

思路分析

多项式乘法匹配字符串是个很经典的技巧，将$t$串翻转，然后做卷积。

设$f(i)$表示$\text{s}$串以$\text{i}$结尾的子串，与$\text{t}$串匹配了多少个字符，考虑对$[0,9]$中每个字符$\text{x}$分别匹配一次。

设$A(x),B(x)$两个多项式分别表示$\text{s}$串和$\text{t}$串，如果$s_i = x$或者$s_i = * $，那么$A(i) = 1$否则$A(i)=0$，$t$串的情况同理，然后两个多项式相乘得到多项式$C(x)$，那么$C(i)$就是$\text{x}$字符的匹配个数，$f(i)=\sum_{x=0}^{9}C(i)$

但是我们发现，答案会多算一部分，如果一个位置$\text{s}$和$\text{t}$都是$ * $ 的话，那么这个位置就会被计算$10$次，所以我们还需要减去多算的部分，单独对 $ * $ 再做一次，$f(i) =f(i) - 9\times C(i)$，最后对于每个匹配个数，再做一遍前缀和输出答案就行了

AC代码

#include <bits/stdc++.h>
#define V vector
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) (x)&(-x)
#define sz(x) (int)(x).size()
#define each(x,a) for(auto& x:a)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
const int N = 4e6+10;
const int P = 998244353;
const int G = 3,Gi = 332748118;

int n,m;
int limit = 1,mcnt,rev[N];
ll a[N],b[N];

ll qpow(ll x,ll k) {
    ll res = 1;
    while(k) {
        if(k&1) res = (res*x)%P;
        x = (x*x)%P;
        k>>=1;
    }
    return res%P;
}

void NTT(ll *A, int type) {
    for(int i = 0; i < limit; i++)
        if(i < rev[i]) swap(A[i], A[rev[i]]);
    for(int mid = 1; mid < limit; mid <<= 1) {
        ll Wn = qpow( type == 1 ? G : Gi , (P - 1) / (mid << 1));
        for(int j = 0; j < limit; j += (mid << 1)) {
            ll w = 1;
            for(int k = 0; k < mid; k++, w = (w * Wn) % P) {
                int x = A[j + k], y = w * A[j + k + mid] % P;
                A[j + k] = (x + y) % P;
                A[j + k + mid] = (x - y + P) % P;
            }
        }
    }
    if(type == -1){
        ll inv = qpow(limit,P-2);
        for(int i=0;i<=limit;i++) A[i] = (A[i]*inv)%P;
    }
}

char s[N],t[N];
ll res[N],sum[N];


signed main() {

#ifdef xiaofan
    clock_t stTime = clock();
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
/*==========================begin============================*/
    IOS;
    int T;
    cin>>T;
    while(T--){
        int n,m;
        cin>>n>>m;
        cin>>s;
        cin>>t;
        reverse(t,t+m);
        limit = 1,mcnt = 0;
        while(limit <= n + m) limit <<= 1, mcnt ++ ;
        for(int i = 0; i < limit; ++ i)
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (mcnt - 1));
        for(int i=0;i<=limit;i++) res[i] = 0;
        for(char x='0';x<='9';x++){
            for(int i=0;i<=limit;i++) a[i] = b[i] = 0;
            for(int i=0;i<n;i++){
                if(s[i]==x || s[i]=='*') a[i] = 1;
                else a[i] = 0;
            }
            for(int i=0;i<m;i++){
                if(t[i]==x || t[i]=='*') b[i] = 1;
                else b[i] = 0;
            }
            NTT(a,1);
            NTT(b,1);
            for(int i=0;i<=limit;i++) a[i] = (a[i]*b[i])%P;
            NTT(a,-1);
            for(int i=0;i<=limit;i++) res[i]+=a[i];
        }

        for(int i=0;i<=limit;i++) a[i] = b[i] = 0;
        for(int i=0;i<n;i++){
            if(s[i]=='*') a[i] = 1;
            else a[i] = 0;
        }
        for(int i=0;i<m;i++){
            if(t[i]=='*') b[i] = 1;
            else b[i] = 0;
        }
        NTT(a,1);
        NTT(b,1);
        for(int i=0;i<=limit;i++) a[i] = (a[i]*b[i])%P;
        NTT(a,-1);
        for(int i=0;i<=limit;i++) res[i]-=9*a[i];
        for(int i=m-1;i<n;i++){
            int ch = m-res[i];
           if(ch>=0) sum[ch]++;
        }
        for(int i=1;i<=m+1;i++) {
            sum[i]+=sum[i-1];
            cout<<sum[i-1]<<"\n";
        }
        for(int i=0;i<=m+1;i++) sum[i] = 0;
         
    }


/*===========================end=============================*/
#ifdef xiaofan
    cerr << "Time Used:" << clock() - stTime << "ms" <<endl;
#endif
    return 0;
}