【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=4503

【题目大意】

  给出S串和T串,计算T在S中出现次数,T中有通配符'?'。

【题解】

  我们定义f[x]=sum_{i=0}^{n-1}|s1[i]-s2[i]|,当f[x]=0时,两个字符串相等。因为考虑到这里还有适配符,所以用f[x]=sum_{i=0}^{n-1}(s1[i]-s2[i])*(s1[i]-s2[i])*s1[i]*s2[i]来表示匹配函数。我们可以发现,如果将一个串倒置,那么这就是一个卷积的式子。因此我们将多项式展开,将得到的相加的三段式子,做三次FFT,将结果汇总,然后统计即可。

【代码】

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=1048600;
int n,pos[N];
namespace FFT{
struct comp{
double r,i;
comp(double _r=0,double _i=0):r(_r),i(_i){}
comp operator +(const comp&x){return comp(r+x.r,i+x.i);}
comp operator -(const comp&x){return comp(r-x.r,i-x.i);}
comp operator *(const comp&x){return comp(r*x.r-i*x.i,i*x.r+r*x.i);}
comp conj(){return comp(r,-i);}
}A[N],B[N];
const double pi=acos(-1.0);
void FFT(comp a[],int n,int t){
for(int i=1;i<n;i++)if(pos[i]>i)swap(a[i],a[pos[i]]);
for(int d=0;(1<<d)<n;d++){
int m=1<<d,m2=m<<1;
double o=pi*2/m2*t;
comp _w(cos(o),sin(o));
for(int i=0;i<n;i+=m2){
comp w(1,0);
for(int j=0;j<m;j++){
comp& A=a[i+j+m],&B=a[i+j],t=w*A;
A=B-t;B=B+t;w=w*_w;
}
}
}if(t==-1)for(int i=0;i<n;i++)a[i].r/=n;
}
}
int l1,l2,ans[N],cnt=0,a[N],b[N];
FFT::comp A[N],B[N],C[N];
char s1[N],s2[N];
int main(){
scanf(" %s %s",&s1,&s2);
l1=strlen(s1); l2=strlen(s2);
for(int i=0;i<l1;i++)a[i]=s1[i]-'a'+1;
for(int i=0;i<l2;i++)b[l2-1-i]=s2[i]=='?'?0:s2[i]-'a'+1;
int N=1; while(N<l1+l2)N<<=1;
int j=__builtin_ctz(N)-1;
for(int i=0;i<N;i++){pos[i]=pos[i>>1]>>1|((i&1)<<j);}
for(int i=0;i<N;i++)A[i]=FFT::comp(a[i]*a[i]*a[i],0),B[i]=FFT::comp(b[i],0);
FFT::FFT(A,N,1);FFT::FFT(B,N,1);
for(int i=0;i<N;i++)C[i]=C[i]+A[i]*B[i];
for(int i=0;i<N;i++)A[i]=FFT::comp(a[i],0),B[i]=FFT::comp(b[i]*b[i]*b[i],0);
FFT::FFT(A,N,1);FFT::FFT(B,N,1);
for(int i=0;i<N;i++)C[i]=C[i]+A[i]*B[i];
for(int i=0;i<N;i++)A[i]=FFT::comp(a[i]*a[i],0),B[i]=FFT::comp(b[i]*b[i],0);
FFT::FFT(A,N,1);FFT::FFT(B,N,1);
for(int i=0;i<N;i++)C[i]=C[i]-A[i]*B[i]*FFT::comp(2,0);
FFT::FFT(C,N,-1);
for(int i=l2-1;i<l1;i++){
if(C[i].r<0.5)ans[cnt++]=i-l2+1;
}printf("%d\n",cnt);
for(int i=0;i<cnt;i++)printf("%d\n",ans[i]);
return 0;
}

  

最新文章

  1. 即学即会 Java 程序设计基础视频教程(100课整)无水印版
  2. 查看linux僵尸进程
  3. vs2013下自动注释的运用
  4. ESXI安装
  5. 【2】认识Bootstrap
  6. codeforces 278Div1 B题
  7. Agri-Net poj 1258
  8. 织梦DEDECMS小说模块使用和安装全攻略
  9. C#共享内存实例 附源码
  10. 简洁AngularJS框架后台管理系统bootstrap后台模板
  11. nginx服务器上遇到了acces denied,报错是fastCGI只要好好修改配置就行了
  12. toupper函数及一些小程序
  13. (转)@ContextConfiguration注解说明
  14. 使用HTML语言和CSS开发商业站点
  15. 关于FusionCharts图表宽度width的设置问题导致图表显示异常的解决办法
  16. Apache服务安全加固
  17. Ajax 学习 第三篇
  18. 大道至简第一章和java理论学时第一节。感受。
  19. 【TensorFlow】:解决TensorFlow的ImportError: DLL load failed: 动态链接库(DLL)初始化例程失败
  20. linux和windows共享文件,通过samba

热门文章

  1. python打包成.exe工具py2exe0-----No such file or directory错误
  2. php不同形式的实现a-z的26个字母的输出
  3. 如何将js与HTML完全脱离
  4. struts2笔记08-初识ActionSupport
  5. 编程工具篇——Vim
  6. c++中vector与list的区别
  7. 限定只能处理&quot;A仓&quot;和&quot;B仓&quot;入库
  8. sql server 2012 镜像和出现的问题
  9. visual leak dector内存泄漏检测方法
  10. (13)[Xamarin.Android] 不同分辨率下的图片使用概论