链接传送门
这题比赛上做出来的人挺多的，于是我就一直在想SAM，结果这是一道用FFT解决的字符串模糊匹配的板子题。
话说我很久以前还写过luogu P4173 残缺的字符串这道题，和比赛的题很像。
首先能想到的是，对于长度为\(m\)的每个\(S\)的子串，我们只要统计其与\(T\)匹配的位置数\(f_i\)，即可以得到该子串被认为匹配的最小的\(k\)值。
对于求\(f_i\)：先不考虑通配符的影响，因为字符集只有'0'~'9'，所以我们可以每个字符单独考虑。拿'0'为例，将\(S,T\)所有是'0'的地方置为\(1\)，其他为\(0\)，则$$f(x)=\sum\limits_{i=0}^{m-1}T(i)*S(x-m+1+i)$$
按照套路，将\(T\)反转，即\(T(i)=T'(m - i - 1)\)，则$$f(x)=\sum\limits_{i=0}^{m-1}T'(m - i - 1) * S(x - m + i + 1)$$会发现等式右边括号内的和刚好是\(x\)，变量代换得$$f(x) = \sum\limits_{j=0}^{m - 1}T'(j) * S(x-j)$$这几乎就是卷积的形式了，只不过卷积的上界是\(x\)，但到\(x\)和到\(m-1\)实际上是没有区别的，因此用对'0'~'9'依次用一遍FFT，就能求出\(f(i)\)了。
现在考虑通配字符，\(S\)的一个子串通过通配字符与\(T\)匹配的位置数=该子串的通配字符数+\(T\)中通配字符数-该子串和\(T\)中同一位置都是通配字符的数量。该子串的通配字符数用前缀和求得，该淄川和\(T\)中同一位置都是通配字符的数量同样同FFT可以求得。#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<assert.h>
#include<ctime>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 5.5e5 + 5;
const db PI = acos(-1);
In ll read()
{
ll ans = 0;
char ch = getchar(), las = ' ';
while(!isdigit(ch)) las = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(las == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
In void MYFILE()
{
#ifndef mrclr
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
}
int n, m;
char s[maxn], t[maxn];
int len = 1, lim = 0, rev[maxn];
struct Comp
{
db x, y;
In Comp operator + (const Comp& oth)const {return (Comp){x + oth.x, y + oth.y};}
In Comp operator - (const Comp& oth)const {return (Comp){x - oth.x, y - oth.y};}
In Comp operator * (const Comp& oth)const {return (Comp){x * oth.x - y * oth.y, x * oth.y + y * oth.x};}
friend In void swap(Comp &a, Comp& b) {swap(a.x, b.x), swap(a.y, b.y);}
}A[maxn], B[maxn];
In void fft(Comp* a, int flg)
{
for(int i = 0; i < len; ++i) if(i < rev[i]) swap(a[i], a[rev[i]]);
for(int i = 1; i < len; i <<= 1)
{
Comp omg = (Comp){cos(PI / i), sin(PI / i) * flg};
for(int j = 0; j < len; j += (i << 1))
{
Comp o = (Comp){1, 0};
for(int k = 0; k < i; ++k, o = o * omg)
{
Comp tp1 = a[k + j], tp2 = o * a[k + j + i];
a[k + j] = tp1 + tp2, a[k + j + i] = tp1 - tp2;
}
}
}
}
int f[maxn], g[maxn], f1[maxn], ans[maxn];
//f[i]：即题解中的f[i]
//g[i]：以i结尾的子串和T同一位置都是通配字符的数量
//f1[i]：S中通配字符数量的前缀和
In void solve()
{
reverse(t, t + m);
len = 1, lim = 0;
while(len <= n + m) len <<= 1, ++lim;
fill(f, f + n, 0);
for(int i = 0; i < len; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (lim - 1));
for(int x = 0; x <= 10; ++x)
{
for(int i = 0; i < len; ++i) A[i] = B[i] = (Comp){0, 0};
char c = x == 10 ? '*' : x + '0';
for(int i = 0; i < n; ++i) if(s[i] == c) A[i].x = 1;
for(int i = 0; i < m; ++i) if(t[i] == c) B[i].x = 1;
fft(A, 1), fft(B, 1);
for(int i = 0; i < len; ++i) A[i] = A[i] * B[i];
fft(A, -1);
for(int i = 0; i < n; ++i)
if(x == 10) g[i] = A[i].x / len + 0.5;
else f[i] += A[i].x / len + 0.5;
}
int f2 = 0;
for(int i = 0; i < n; ++i) f1[i] = (i ? f1[i - 1] : 0) + (s[i] == '*');
for(int i = 0; i < m; ++i) f2 += (t[i] == '*');
fill(ans, ans + m + 1, 0);
for(int i = m - 1; i < n; ++i) ans[m - (f[i] + f1[i] - (i < m ? 0 : f1[i - m]) + f2 - g[i])]++;
for(int i = 0; i <= m; ++i)
{
if(i) ans[i] += ans[i - 1];
write(ans[i]), enter;
}
}
int main()
{
int T = read();
while(T--)
{
n = read(), m = read();
scanf("%s%s", s, t);
solve();
}
return 0;
}
|
编程语言
发布于：2021-07-31 18:09
|
阅读数：220
|
评论：0
QQ好友和群
QQ空间
