题目:https://www.lydsy.com/JudgeOnline/problem.php?id=4503

推式子即可;

不知怎的调了那么久,应该是很清晰的。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double db;
int const xn=(<<);
db const Pi=acos(-1.0);
char S[xn],T[xn];
int n,m,lim,s[xn],t[xn],rev[xn],w[xn];
struct com{db x,y;}a[xn],b[xn];
com operator + (com a,com b){return (com){a.x+b.x,a.y+b.y};}
com operator - (com a,com b){return (com){a.x-b.x,a.y-b.y};}
com operator * (com a,com b){return (com){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
void init()
{
int l=; lim=;
while(lim<=n+m)lim<<=,l++;
for(int i=;i<lim;i++)
rev[i]=((rev[i>>]>>)|((i&)<<(l-)));
}
void fft(com *a,int tp)
{
for(int i=;i<lim;i++)
if(i<rev[i])swap(a[i],a[rev[i]]);
for(int mid=;mid<lim;mid<<=)
{
com wn=(com){cos(Pi/mid),tp*sin(Pi/mid)};
for(int j=,len=(mid<<);j<lim;j+=len)
{
com w=(com){,};
for(int k=;k<mid;k++,w=w*wn)
{
com x=a[j+k],y=w*a[j+mid+k];
a[j+k]=x+y; a[j+mid+k]=x-y;
}
}
}
}
int main()
{
scanf("%s",S); n=strlen(S)-;
scanf("%s",T); m=strlen(T)-;
init();
for(int i=;i<=n;i++)s[i]=S[i]-'a'+;
int tmp=;
for(int i=;i<=m;i++)
{
t[i]=(T[m-i]=='?'?:T[m-i]-'a'+);
tmp+=t[i]*t[i]*t[i];
}
for(int i=;i<=n;i++)a[i].x=s[i]*s[i];
for(int i=;i<=m;i++)b[i].x=t[i];
fft(a,); fft(b,);
for(int i=;i<lim;i++)a[i]=a[i]*b[i];
fft(a,-);
for(int i=;i<lim;i++)w[i]=(int)(a[i].x/lim+0.5)+tmp; for(int i=;i<=lim;i++)a[i].x=a[i].y=b[i].x=b[i].y=;
for(int i=;i<=n;i++)a[i].x=*s[i];
for(int i=;i<=m;i++)b[i].x=t[i]*t[i];
fft(a,); fft(b,);
for(int i=;i<lim;i++)a[i]=a[i]*b[i];
fft(a,-);
for(int i=;i<lim;i++)w[i]-=(int)(a[i].x/lim+0.5); int num=;
for(int i=m;i<=n;i++)if(w[i]==)num++;//
printf("%d\n",num);
for(int i=m;i<=n;i++)
if(w[i]==)printf("%d\n",i-m);
return ;
}

最新文章

  1. 利用AOP写2PC框架(一)
  2. rsync同步
  3. 正则匹配闭合HTML标签(支持嵌套)
  4. java轻量级IOC框架Guice
  5. SpringMVC和MyBatis整合
  6. (转载)Javascript定义类(class)的三种方法
  7. f2fs解析(三)NAT中如何区分inode和其他dnode
  8. Web Server PROPFIND Method internal IP Discosure
  9. Nginx——在Windows环境下安装
  10. 10. 面向holder编程、自动轮询
  11. idea 过段时间java程序包不存在问题 ?
  12. 【jQuery】(2)---Jquery过滤选择器
  13. Weex小笔记(自己理解,有错请指正)
  14. 福州大学第十五届程序设计竞赛_重现赛B题迷宫寻宝
  15. PHP 5.2、5.3、5.4、5.5、5.6 对比以及功能详解
  16. User-Defined Table Types 用户自定义表类型
  17. frame标签使用
  18. 【WPF】MVVM前台绑定一组RadioButton按钮
  19. 原生js创建模态框
  20. 完善String类([]、 +、 += 运算符重载)、&gt;&gt;和&lt;&lt;运算符重载

热门文章

  1. Git安装及SSH Key管理之Windows篇
  2. C#中??和?分别是什么意思? 在ASP.NET开发中一些单词的标准缩写 C#SESSION丢失问题的解决办法 在C#中INTERFACE与ABSTRACT CLASS的区别 SQL命令语句小技巧 JQUERY判断CHECKBOX是否选中三种方法 JS中!=、==、!==、===的用法和区别 在对象比较中,对象相等和对象一致分别指的是什么?
  3. Android pull to Refresh 导入出错?
  4. Android调用JNI本地方法跟踪目标代码
  5. kubernetes集群管理命令(三)
  6. 动态控制body最小高度
  7. python pyinotify模块详解
  8. javascript点滴积累
  9. SDP, RTP, RTCP, RTSP, RTMP 名词解释
  10. JavaScript+Json写的二级联动