【CF528D】Fuzzy Search

╰半夏微凉° 2023-08-17 15:48 143阅读 0赞

# Problem #

## Description ##

你有一个长度为 \\(n\\) 的串 \\(S\\)，以及长度为 \\(m\\) 的串 \\(T\\)。

现给定一个数 \\(k\\) ，我们说 \\(T\\) 在 \\(S\\) 的位置 \\(i\\) 匹配上，当且仅当对于每一个 \\(1\\le a\\le m\\) ，都有一个位置 \\(1\\le b\\le n\\) 满足 \\(|(i+a-1)-b|\\le k\\) ，且 \\(S\_b=T\_a\\) 。

请回答 \\(T\\) 在 \\(S\\) 中匹配上了多少个不同的位置。

## Range ##

\\(n,m,k\\le2\*10^5\\)

# Algorithm #

\\(FFT\\)

# Mentality #

思路很妙的说。

先考虑 \\(k=0\\) 的情况。不难发现，当 \\(T\\) 与 \\(S\\) 匹配上时，\\(T\\) 中的每个字符与 \\(S\\) 中对应匹配字符的 **位置的差** 是相等的。

同时考虑在多项式乘法中，若许多对项最后会贡献在同一个位置上，那么它们的 **次方的和** 是相等的。

则考虑倒转原串，得到 \\(T'\\) 。

由于字符集大小仅仅为 \\(4\\) ，我们可以尝试一下分开考虑每种不同的字符。

对于当前字符 \\(c\\)，考虑设 \\(f\_i=\[S\_i==c\]\*x^i\\)，\\(g\_i=\[T'\_i==c\]\*x^i\\)。

则对于得到的 \\(F(x)=f(x)\*g(x)\\) 而言，我们发现对于原串中的字符 \\(S\_i=T\_j=c\\) ，它们在 \\(f\\) 与 \\(g\\) 中对应项的乘积为 \\(1\\) ，且对位置 \\(m-j+1+i\\) 产生了 \\(1\\) 的贡献。

对于下一种字符 \\(p\\) 而言，若有 \\(S\_\{i+1\}=T\_\{j+1\}=p\\)，则会对 \\(m-(j+1)+1+(i+1)=m-j+1+i\\) 有 \\(1\\) 的贡献。

换句话说，若有 \\(T\\) 在 \\(S\\) 的位置 \\(i\\) 匹配上了，那么必定有：\\(T\_1=S\_i,T\_2=S\_\{i+1\}\\dots T\_m=S\{i+m-1\}\\) ，也就必定会在对四种字符的卷积里对 \\(m-j+1+i\\) 这一项总共产生 \\(m\\) 的贡献。

将四次卷积的结果相加，则最后的答案为：系数为 \\(m\\) 的项的个数。

接着考虑 \\(k>0\\) 的情况，我们会发现和 \\(k=0\\) 的思路几乎一致，对于这个 \\(k\\) ，想想它的意义：我们在处理每种不同的字符的时候，若当前字符为 \\(c\\) ，对于每个为 \\(c\\) 的位置，它往左右两边 \\(k\\) 位也都是可以匹配的位置。

那我们直接将每个 \\(c\\) 的左右 \\(k\\) 位也都设成 \\(c\\) 不就好了嘛？

那么思路就很清晰了：四种字符分别统计，然后对于每种当前统计的字符，将左右 \\(k\\) 位设为同样的字符，得到 \\(f,g\\) 两个多项式，并将其卷积得到 \\(F(x)=f(x)\*g(x)\\) ，将四个 \\(F(x)\\) 相加，统计系数为 \\(m\\) 的项数。

完毕。

# Code #

#include <cmath> #include <cstdio> #include <cstring> #include <iostream> using namespace std; #define LL long long #define go(x, i, v) for (int i = hd[x], v = to[i]; i; v = to[i = nx[i]]) #define inline __inline__ __attribute__((always_inline)) LL read() { long long x = 0, w = 1; char ch = getchar(); while (!isdigit(ch)) w = ch == '-' ? -1 : 1, ch = getchar(); while (isdigit(ch)) { x = (x << 3) + (x << 1) + ch - '0'; ch = getchar(); } return x * w; } const int Max_n = 2e5 + 5, mod = 998244353, G = 3; int n, m, K, ans; int f[Max_n << 2], g[Max_n << 2], A[Max_n << 2]; int lim, bit, rev[Max_n << 2]; char S[Max_n], T[Max_n]; inline void Convert(char &c) { if (c == 'A') c = 'a'; if (c == 'C') c = 'b'; if (c == 'G') c = 'c'; if (c == 'T') c = 'd'; } inline int ksm(int a, int b) { int res = 1; for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) res = 1ll * res * a % mod; return res; } namespace NTT { inline void dft(int *f, bool t) { for (int i = 0; i < lim; i++) if (rev[i] > i) swap(f[i], f[rev[i]]); for (int len = 1; len < lim; len <<= 1) { int Wn = ksm(G, (mod - 1) / (len << 1)); if (t) Wn = ksm(Wn, mod - 2); for (int i = 0; i < lim; i += len << 1) { int Wnk = 1; for (int k = i; k < i + len; k++, Wnk = 1ll * Wnk * Wn % mod) { int x = f[k], y = 1ll * f[k + len] * Wnk % mod; f[k] = (x + y) % mod, f[k + len] = (x - y + mod) % mod; } } } } } // namespace NTT inline void ntt(int *f, int *g) { NTT::dft(f, 0), NTT::dft(g, 0); for (int i = 0; i < lim; i++) f[i] = 1ll * f[i] * g[i] % mod; NTT::dft(f, 1); int Inv = ksm(lim, mod - 2); for (int i = 0; i < lim; i++) f[i] = 1ll * f[i] * Inv % mod; } int main() { #ifndef ONLINE_JUDGE freopen("D.in", "r", stdin); freopen("D.out", "w", stdout); #endif n = read(), m = read(), K = read(); scanf(" %s", S + 1), scanf("%s", T + 1); for (int i = 1; i <= n; i++) Convert(S[i]); for (int i = 1; i <= m; i++) Convert(T[i]); for (int i = 1; i <= m / 2; i++) swap(T[i], T[m - i + 1]); bit = log2(n + m) + 1, lim = 1 << bit; for (int i = 0; i < lim; i++) rev[i] = rev[i >> 1] >> 1 | ((i & 1) << (bit - 1)); for (int k = 'a'; k <= 'd'; k++) { memset(f, 0, sizeof(f)), memset(g, 0, sizeof(g)); for (int i = 1, cnt = 0; i <= n; i++) { if (S[i] == k) cnt = K, f[i] = 1; else if (cnt) cnt--, f[i] = 1; } for (int i = n, cnt = 0; i >= 1; i--) { if (S[i] == k) cnt = K, f[i] = 1; else if (cnt) cnt--, f[i] = 1; } for (int i = 1; i <= m; i++) g[i] = T[i] == k; ntt(f, g); for (int i = 0; i < lim; i++) A[i] += f[i]; } for (int i = 0; i < lim; i++) ans += A[i] == m; cout << ans; }

转载于:https://www.cnblogs.com/luoshuitianyi/p/11486383.html