題目鏈接：點擊查看

題目大意：給出一個長度為 $n$ 的字符串 $s$ 和一個長度為 $m$ 的字符串 $t$，問字符串 $s$ 有哪些子串可以匹配 $t$。給出一個參數(shù) $k$，$T$ 在 $S$ 的第 $i$ 個位置中出現(xiàn)，當(dāng)且僅當(dāng)把 $T$ 的首字符和 $S$ 的第 $i$ 個字符對齊后，$T$ 中的每一個字符能夠在 $S$ 中找到一個位置偏差不超過 $k$ 的相同字符。

需要注意的是，在字符串 $s$ 中通過偏差匹配的字符可以重復(fù)與 $t$ 匹配

題目分析：預(yù)處理出數(shù)組 $g[i][j]$，代表字符串 $s$ 的第 $i$ 個位置可以放置字符 $j$，然后就是套路了：枚舉每個字符，將字符串 $t$ 反轉(zhuǎn)，用 $NTT$ 處理出數(shù)組 $f(x)$ 代表子串 $s[x?m+1:x]$ 與字符串 $t$ 可以匹配的位置，最后需要統(tǒng)計 $f(i)=m$ 的個數(shù)

代碼：

// Problem: D. Fuzzy Search // Contest: Codeforces - Codeforces Round #296 (Div. 1) // URL: https://codeforces.com/contest/528/problem/D // Memory Limit: 256 MB // Time Limit: 3000 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> #include<list> #include<unordered_map> #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,k,limit=1,L,r[N<<2]; LL a[N<<2],b[N<<2],f[N<<2]; char s[N],t[N]; 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() {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)); } void solve(char ch) {for(int i=0;i<limit;i++) {a[i]=b[i]=0;}int last=-inf;for(int i=0;i<n;i++) {if(s[i]==ch) {last=i;}if(i-last<=k) {a[i]=1;}}last=inf;for(int i=n-1;i>=0;i--) {if(s[i]==ch) {last=i;}if(last-i<=k) {a[i]=1;}}for(int i=0;i<m;i++) {b[i]=t[i]==ch;}NTT(a,1),NTT(b,1);for(int i=0;i<limit;i++) {f[i]=(f[i]+a[i]*b[i])%mod;} } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);read(n),read(m),read(k);init();scanf("%s%s",s,t);reverse(t,t+m);solve('A'),solve('C'),solve('G'),solve('T');NTT(f,-1);LL inv=fastpow(limit,mod-2);for(int i=0;i<=n+m;i++) {f[i]=(f[i]*inv)%mod;}int ans=0;for(int i=m-1;i<n;i++) {ans+=f[i]==m;}cout<<ans<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 528D Fuzzy Search(多项式匹配字符串)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。