字符串模糊匹配(带通配符)
题目见 hdu forgiving match
#include <bits/stdc++.h>
#define rep(int i,int l,int r) for(int i = l; i <= r ;i ++)
using namespace std;
const int N = 524288;
const int mod = 998244353;
const int inf = 0x3fffffff;
typedef long long ll;
int T;
int n, m;
char s[N], t[N];
int pw(int x, int y)
{
int ret = 1;
while (y)
{
if (y & 1) ret = 1ll * ret * x % mod;
x = 1ll * x * x % mod;
y >>= 1;
}
return ret;
}
int inv(int x) { return pw(x, mod - 2); }
int rev[N];
void get_rev(int n) { // rearrange the sequence
int bit = 0;
while ((1 << bit) < n) ++bit;
rev[0] = 0;
for (int i = 1; i < n; ++i) {
rev[i] = rev[i >> 1] >> 1 | (i & 1) << bit - 1;
}
}
void DFT(int *a, int n, int dir) { // dir=1: DFT, dir=-1:IDFT
for (int i = 0; i < n; ++i) {
if (i < rev[i]) swap(a[i], a[rev[i]]);
}
for (int len = 1; len < n; len <<= 1) {
int wn = pw(3, (mod - 1) / (len << 1));
if (dir == -1) wn = inv(wn);
for (int i = 0; i < n; i += len << 1) {
int w = 1;
for (int j = i; j < i + len; ++j) {
int t = 1ll * a[j + len] * w % mod;
a[j + len] = (a[j] - t + mod) % mod;
a[j] = (a[j] + t) % mod;
w = 1ll * w * wn % mod;
}
}
}
int inv_n = inv(n);
if (dir == -1) {
for (int i = 0; i < n; ++i) a[i] = 1ll * a[i] * inv_n % mod;
}
}
void mul(int *a, int *b, int n, int *c) {
DFT(a, n, 1);
DFT(b, n, 1);
rep(i, 0, n - 1) { c[i] = 1ll * a[i] * b[i] % mod; }
DFT(c, n, -1);
}
int t1[N], t2[N], t3[N];
int par[N];
int ans[N];
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);//长度为 n 的主串 长度为 m 的子串
scanf("%s%s", s, t);
int lim = 1;
while (lim < n + m) lim <<= 1;
get_rev(lim);
rep(i, 0, n - m) par[i] = 0;
for (char c = '0'; c <= '9'; ++c)// 枚举每一种字符 对其做匹配
{
rep(i, 0, lim - 1)
{
t1[i] = (i < n && s[i] == c) ? 1 : 0;// 0 ~ 9 为 1 通配符为 0
t2[i] = (i < m && t[m - 1 - i] == c) ? 1 : 0;//倒着匹配 0 ~ 9 为 1 通配符为 0
}
mul(t1, t2, lim, t3);//对所有的 0 ~ 9 字符做 FFT
rep(i, 0, n - m)//枚举子串每种匹配情况对应的值
{
par[i] += t3[i + m - 1];//par[i] 子串的第一个字符从第 i 个位置开始匹配的匹配值
//为什么是 i + m - 1 咧
//因为倒着匹配时 最低的阶数为 m - 1 (子串的最后一个数和主串第一个数匹配) 最高的阶数为 n - 1 (子串第一个数和主串最后一个数匹配)
}
}
rep(i, 0, lim - 1)
{
t1[i] = (i < n && s[i] == '*') ? 1 : 0;//主串通配符对其他字符的贡献
t2[i] = (i < m) ? 1 : 0;
}
mul(t1, t2, lim, t3);
rep(i, 0, n - m) par[i] += t3[i + m - 1];
rep(i, 0, lim - 1)
{
t1[i] = (i < n) ? 1 : 0;
t2[i] = (i < m && t[m - 1 - i] == '*') ? 1 : 0;//子串通配符对其他字符的贡献
}
mul(t1, t2, lim, t3);
rep(i, 0, n - m) par[i] += t3[i + m - 1];
rep(i, 0, lim - 1)
{
t1[i] = (i < n && s[i] == '*') ? 1 : 0;//通配符对通配符的贡献
t2[i] = (i < m && t[m - 1 - i] == '*') ? 1 : 0;
}
mul(t1, t2, lim, t3);
rep(i, 0, n - m) par[i] -= t3[i + m - 1];//减去重复计算的通配符对通配符的贡献
rep(i, 0, m) ans[i] = 0;
rep(i, 0, n - m)
{
//printf("%d ", par[i]);
//par[i]是能匹配上的
//需要容忍 m - par[i] 个字符
ans[m - par[i]]++;
}
//ans[i] : 容忍 i 个错误时能匹配上的可能性
rep(i, 1, m) ans[i] += ans[i - 1];
rep(i, 0, m) printf("%d\n", ans[i]);
}
return 0;
}
多项式乘法
#include<bits/stdc++.h>
using namespace std;
const double PI=acos(-1.0);
struct Complex
{
double x,y;
Complex (double _x=0.0 ,double _y=0.0)
{
x=_x;
y=_y;
}
Complex operator -(const Complex &b) const
{
return Complex (x-b.x,y-b.y);
}
Complex operator +(const Complex &b) const
{
return Complex(x+b.x,y+b.y);
}
Complex operator *(const Complex &b) const
{
return Complex(x*b.x-y*b.y,x*b.y+y*b.x);
}
};
void change(Complex y[],int len)
{
int i,j,k;
for(int i=1,j=len/2;i<len-1;i++)
{
if(i<j) swap(y[i],y[j]);
k=len/2;
while(j>=k)
{
j-=k;
k/=2;
}
if(j<k) j+=k;
}
}
void fft(Complex y[],int len,int on)
{
change(y,len);
for(int h = 2; h <= len; h <<= 1)
{
Complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));
for(int j=0;j<len;j+=h)
{
Complex w(1,0);
for(int k=j;k< j+h/2;k++)
{
Complex u = y[k];
Complex t = w*y[k+h/2];
y[k]=u+t;
y[k+h/2]=u-t;
w=w*wn;
}
}
}
if(on== -1)
for(int i=0;i<len;i++)
y[i].x/=len;
}
// const int N = ?(? 为满足数据范围的2的次幂)
//ex. n 为 1e5 则 我们取? = (1<<18) 262144 要比给的 n 大两倍
//Complex x1[N],x2[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<=n;i++)
{
int x;
cin>>x;
x1[i]=Complex(x,0);
}
for(int j=0;j<=m;j++)
{
int x;
cin>>x;
x2[j]=Complex(x,0);
}
// int len = ? ; len的取值与N同理
fft(x1,len,1);
fft(x2,len,1);
for(int i=0;i<len;i++)
x1[i]=x1[i]*x2[i];
fft(x1,len,-1);
// for(int i=0;i<=n+m;i++)
//printf("%.0lf ",abs(x1[i].x)); //多项式乘法
return 0;
}
高精度乘法
#include<bits/stdc++.h>
using namespace std;
const double PI=acos(-1.0);
struct Complex
{
double x,y;
Complex (double _x=0.0 ,double _y=0.0)
{
x=_x;
y=_y;
}
Complex operator -(const Complex &b) const
{
return Complex (x-b.x,y-b.y);
}
Complex operator +(const Complex &b) const
{
return Complex(x+b.x,y+b.y);
}
Complex operator *(const Complex &b) const
{
return Complex(x*b.x-y*b.y,x*b.y+y*b.x);
}
};
void change(Complex y[],int len)
{
int i,j,k;
for(int i=1,j=len/2;i<len-1;i++)
{
if(i<j) swap(y[i],y[j]);
k=len/2;
while(j>=k)
{
j-=k;
k/=2;
}
if(j<k) j+=k;
}
}
void fft(Complex y[],int len,int on)
{
change(y,len);
for(int h = 2; h <= len; h <<= 1)
{
Complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));
for(int j=0;j<len;j+=h)
{
Complex w(1,0);
for(int k=j;k< j+h/2;k++)
{
Complex u = y[k];
Complex t = w*y[k+h/2];
y[k]=u+t;
y[k+h/2]=u-t;
w=w*wn;
}
}
}
if(on== -1)
for(int i=0;i<len;i++)
y[i].x/=len;
}
const int N = 262144 ;
Complex x1[N],x2[N];
char str1[N/2],str2[N/2];
int sum[N];
int main()
{
scanf("%s%s",str1,str2);
int len1 = strlen(str1);
int len2 = strlen(str2);
int len = 1;
while(len < len1*2 || len < len2*2)len<<=1;
for(int i = 0;i < len1;i++)
x1[i] = Complex(str1[len1-1-i]-'0',0);
for(int i = len1;i < len;i++)
x1[i] = Complex(0,0);
for(int i = 0;i < len2;i++)
x2[i] = Complex(str2[len2-1-i]-'0',0);
for(int i = len2;i < len;i++)
x2[i] = Complex(0,0);
//经典四步曲
fft(x1,len,1);
fft(x2,len,1);
for(int i=0;i<len;i++)
x1[i]=x1[i]*x2[i];
fft(x1,len,-1);
for(int i = 0;i < len;i++)
sum[i] = (int)(x1[i].x+0.5);
for(int i = 0;i < len;i++)
{
sum[i+1]+=sum[i]/10;
sum[i]%=10;
}
len = len1+len2-1;
while(sum[len] <= 0 && len > 0)len--;
for(int i = len;i >= 0;i--)
printf("%c",sum[i]+'0');
return 0;
}
