引入
给你两个字符串 。询问 是否匹配。其中 含有通配符 。 可以匹配任意一种字符。
分析
如果我们使用最常见的字符串匹配算法 我们发现,对于 的处理是非常复杂度的。这个我们引入一个函数 。叫做字符串 的距离函数。那么我们定义 。这样如果我们把 看做完全匹配的话,如果 我们就把他定义为 。这样就完美的解决了通配符的问题。但是由于引入了一个二元函数。我们计算上式子需要的时间复杂度为 。考虑函数展开 如果我们定义 这样我们得到了一个卷积形式。通过 或者 优化。总的复杂度变为 。
代码
#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; }