題目鏈接：點擊查看

題目大意：給出一個長度為 $n$ 的字符串 $s$ 和一個長度為 $m$ 的字符串 $t$。規定 $k$ 匹配的意思是，兩個長度相同的字符串至多有 $k$ 個位置是不同的，特別的，$k=0$ 時指的就是完全匹配?，F在問當 $k\in [0,m]$ 時，字符串 $t$ 可以和字符串中的多少個子串匹配

題目分析：這里簡單分析一下多項式匹配字符串的一般方法。設 $S(i)$ 為字符串 $s$ 的每一位，同理 $T(j)$ 為字符串 $t$ 的每一位，規定 $F(x)$ 為“在字符串 $s$ 中，子串 $s[x?m+1:x]$ 可以與字符串 $t$ 匹配的位數”。自然當 $S(i)=T(j)$ 時，$F(i?j)$ 加一?？紤]將 $t$ 翻轉得到 $T^{\prime }$，易知 $T(j)=T^{\prime }(m?j?1)$，所以當 $S(i)=T^{\prime }(j)$ 時，$F(i?(m?j?1))$ 加一，即 $F((i+j)?m?1)$ 加一，然后枚舉字符集，每次卷積累加就可以統計出答案了，顯然 $m?F(x)$ 代表的就是子串 $s[x?m+1:x]$ 與字符串 $t$ 的失配數了

具體實現方法就是枚舉字符集，將兩個字符串都轉換為 $01$ 串，這樣就可以很方便的通過卷積實現上面的操作了

這種匹配的做法受限于字符集大小，復雜度為 $O(knlogn)$，其中 $k$ 為字符集大小

回到本題，如何處理通配符呢，其實可以單獨處理，對于每個子串而言，通過通配符匹配的字符個數為：S子串中通配符的個數 + T串中通配符的個數 - S子串和T串中通配符匹配的個數

前兩項都可以預處理前綴和維護，第三項可以用多項式像前面一樣處理出來

代碼：

// Problem: Forgiving Matching // Contest: Virtual Judge - HDU // URL: https://vjudge.net/problem/HDU-6975 // Memory Limit: 524 MB // Time Limit: 12000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=2e5+100; const int mod=998244353,G=3,Gi=332748118; int n,m,limit = 1,L,r[N<<2],sum[N],ans[N]; LL a[N<<2],b[N<<2],f[N<<2]; char s[N<<2],t[N<<2]; inline LL fastpow(LL a, LL k) {LL base = 1;while(k) {if(k & 1) base = (base * a ) % mod;a = (a * a) % mod;k >>= 1;}return base % mod; } inline void NTT(LL *A, int type) {for(int i = 0; i < limit; i++) if(i < r[i]) swap(A[i], A[r[i]]);for(int mid = 1; mid < limit; mid <<= 1) { LL Wn = fastpow( type == 1 ? G : Gi , (mod - 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) % mod) {int x = A[j + k], y = w * A[j + k + mid] % mod;A[j + k] = (x + y) % mod,A[j + k + mid] = (x - y + mod) % mod;}}} } void init() {memset(s,0,sizeof(s));memset(t,0,sizeof(t));memset(ans,0,sizeof(ans));memset(sum,0,sizeof(sum));memset(f,0,sizeof(f));limit=1,L=0;while(limit<=n+m) limit<<=1,L++;for(int i=0;i<limit;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(L-1)); } int main() { #ifndef ONLINE_JUDGE// freopen("C:\\Users\\Frozen_Guardian\\Desktop\\1003.in","r",stdin);// freopen("C:\\Users\\Frozen_Guardian\\Desktop\\1003.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--) {read(n),read(m);init();scanf("%s%s",s,t);reverse(t,t+m);for(int k=0;k<=10;k++) {char ch;if(k<10) {ch='0'+k;} else {ch='*';}for(int i=0;i<limit;i++) {a[i]=s[i]==ch;b[i]=t[i]==ch;}NTT(a,1),NTT(b,1);for(int i=0;i<limit;i++) {if(k<10) {f[i]=(f[i]+a[i]*b[i])%mod;} else {f[i]=(f[i]-a[i]*b[i]%mod+mod)%mod;}}}NTT(f,-1);LL inv=fastpow(limit,mod-2);for(int i=0;i<=n+m;i++) {f[i]=(f[i]*inv)%mod;}int cnt=0;for(int i=0;i<m;i++) {cnt+=t[i]=='*';}for(int i=0;i<n;i++) {if(i) {sum[i]+=sum[i-1];}sum[i]+=s[i]=='*';}for(int i=m-1;i<n;i++) {f[i]=(f[i]+sum[i]+cnt)%mod;if(i>=m) {f[i]=(f[i]-sum[i-m]+mod)%mod;}}for(int i=m-1;i<n;i++) {ans[m-f[i]]++;}for(int i=0;i<=m;i++) {if(i) {ans[i]+=ans[i-1];}printf("%d\n",ans[i]);}}return 0; }

總結

以上是生活随笔為你收集整理的HDU多校3 - 6975 Forgiving Matching(多项式匹配字符串)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。