给定串A和串B,A由26个小写字母构成,B由?和26个小写字母构成

?可以和任意字符匹配

求A中出现了多少次B

这里可以使用fft做法,定义向量A和向量B

然后求A和rev(B)的卷积结果C

C的第i-len(B)位就可以表示匹配结果

如果C的第i-len(B)位恰好是B中除了?的字符个数,那么就是匹配成功

这样复杂度就是O((n+m)*(logn + logm))

注意要调整eps,当数据很大的时候,误差会比较大

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <complex>
using namespace std;
const double pi = acos(-);
const int maxn = ;
typedef complex<double> Complex;
const double eps = 1e-;
void DFT(Complex *a, int n, int t)
{
if(n == ) return;
Complex a0[n>>], a1[n>>];
for(int i = ; i < n; i += ) a0[i>>] = a[i], a1[i>>] = a[i+];
DFT(a0, n>>, t); DFT(a1, n>>, t);
Complex wn(cos(*pi/n), t*sin(*pi/n)), w(, );
for(int i = ; i < (n>>); i++, w *= wn) a[i] = a0[i] + w*a1[i], a[i+(n>>)] = a0[i] - w*a1[i];
}
Complex a[maxn], b[maxn];
int n1, n2, nn, c[maxn];
double x;
string s1, s2;
int main()
{
freopen("a.txt", "r", stdin);
cin>>s1>>s2;
n1 = s1.length(); n2 = s2.length();
int N = n2;
for(int i = ; i < n1; i++) x = *pi*(s1[i] - 'a')/, a[i] = Complex(cos(x), sin(x));
for(int i = ; i < n2; i++)
if(s2[i] != '?') x = *pi*(s2[i] - 'a')/, b[i] = Complex(cos(-x), sin(-x));
else b[i] = Complex(, ), N--;
for(int i = ; i < n2/; i++) swap(b[i], b[n2-i-]);
n1--; n2--;
nn = ; while(nn <= n1+n2) nn <<= ;
DFT(a, nn, ); DFT(b, nn, );
for(int i = ; i <= nn; i++) a[i] = a[i]*b[i];
DFT(a, nn, -);
for(int i = ; i <= n1+n2; i++) c[i] = abs(a[i].imag()) < eps ? (a[i].real()/nn + eps) : ;
int ans = ;
for(int i = n2; i <= n1; i++) if(c[i] == N) ans++;
cout<<ans<<endl;
return ;
}

最新文章

  1. golang的内置类型map的一些事
  2. HTML DOM scale() 方法
  3. virtualbox无法安装VBoxLinuxAdditions.run
  4. [Sdoi2014]旅行 题解
  5. math.h--------数学函数
  6. CAP理论(转)
  7. web面试题大全
  8. DB2测试存储过程的原子性
  9. 题目1043:Day of Week(输入日期与当前日起天数差%7,在做相关星期调整)
  10. 基于.NET平台的分布式应用程序的研究
  11. CSS3实现文字描边
  12. 【转】深入理解Java内存模型(二)——重排序
  13. 【Eclipse】web项目部署新手篇
  14. java关于jdbc的配置与使用步骤
  15. Windows上最大传输单元MTU值的查看和设置
  16. poj 1704 Georgia and Bob(阶梯博弈)
  17. ACM Robot Motion
  18. python调试pdb
  19. web进修之—Hibernate HQL(7)
  20. ARM的Jazelle技术【转】

热门文章

  1. xml的schema约束(Java)
  2. visio studio code 用chrom启动打开本地html
  3. Ubuntu 16.04 swoole扩展安装注意!!!
  4. Mongoose模式的扩展
  5. Kubernetes-tutorials(五)
  6. xampps 不能配置非安装目录虚拟主机解决方案
  7. 3468-A Simple Problem with Integers 线段树(区间增减,区间求和)
  8. 从C到C++ (3)
  9. html5判断设备的动作
  10. Autofac小例子