fft

搞一个生成函数

对于每位A(j)=Σi=1->m (a[i]-b[i+j])^2*a[i]*b[i+j]

如果A(j)=0说明这位匹配

如果这位是*那么a[i]=0否则等于字母-'a'+1,b也是这样构造

然后我们翻转a串就可以加速了

#include<bits/stdc++.h>
using namespace std;
#define pi acos(-1)
const int N = ( << ) + ;
int n = , n1, n2, k;
char s1[N], s2[N];
int t[N], ans[N];
struct data {
double a, b;
data() { a = ; b = ; }
data(double _, double __) : a(_), b(__) {}
data friend operator + (const data &a, const data &b) { return data(a.a + b.a, a.b + b.b); }
data friend operator - (const data &a, const data &b) { return data(a.a - b.a, a.b - b.b); }
data friend operator * (const data &a, const data &b) { return data(a.a * b.a - a.b * b.b, a.a * b.b + a.b * b.a); }
} a0[N], b0[N], a1[N], b1[N], a2[N], b2[N];
void fft(data *a, int f)
{
for(int i = ; i < n; ++i)
{
int t = ;
for(int j = ; j < k; ++j) if(i >> j & ) t |= << (k - j - );
if(i < t) swap(a[i], a[t]);
}
for(int l = ; l <= n; l <<= )
{
int m = l >> ;
data w = data(cos(pi / m), f * sin(pi / m));
for(int i = ; i < n; i += l)
{
data t = data(, );
for(int k = ; k < m; ++k, t = t * w)
{
data x = a[i + k], y = t * a[i + k + m];
a[i + k] = x + y;
a[i + k + m] = x - y;
}
}
}
}
int main()
{
scanf("%d%d%s%s", &n1, &n2, s1, s2);
reverse(s1, s1 + n1);
--n1;
--n2;
for(int i = ; i <= n1; ++i) if(s1[i] != '*')
{
double x = s1[i] - 'a' + ;
a0[i] = data(x, );
a1[i] = data(x * x, );
a2[i] = data(x * x * x, );
}
for(int i = ; i <= n2; ++i) if(s2[i] != '*')
{
double x = s2[i] - 'a' + ;
b0[i] = data(x, );
b1[i] = data(- * x * x, );
b2[i] = data(x * x * x, );
}
while(n <= n1 + n2) n <<= , ++k;
fft(a0, );
fft(a1, );
fft(a2, );
fft(b0, );
fft(b1, );
fft(b2, );
for(int i = ; i < n; ++i) a2[i] = a2[i] * b0[i], a1[i] = a1[i] * b1[i], a0[i] = a0[i] * b2[i], a2[i] = a2[i] + a1[i] + a0[i];
fft(a2, -);
for(int i = ; i < n; ++i) t[i] = (int)(a2[i].a / n + 0.1);
for(int i = ; i <= n2 - n1; ++i) if(t[i + n1] == ) ans[++ans[]] = i + ;
printf("%d\n", ans[]);
for(int i = ; i < ans[]; ++i) printf("%d ", ans[i]);
printf("%d\n", ans[ans[]]);
return ;
}

最新文章

  1. Android导包导致java.lang.NoClassDefFoundError
  2. mac rvm升级ruby
  3. 检测Java程序运行时间的2种方法(高精度的时间[纳秒]与低精度的时间[毫秒])
  4. 串 &amp; 容斥原理
  5. IOS开发之代码之九宫格
  6. Java 比较两张图片的相似度
  7. 微软控制台带来的PHP控制台输出问题
  8. Waterfall———瀑布流布局插件, 类似于 Pinterest、花瓣、发现啦。
  9. mws文件中的tab文件改为相对路径
  10. Retrofit网络请求库应用01
  11. hihocoder1388 Periodic Signal
  12. 【Linux】 Linux权限管理与特殊权限
  13. IP地址类型
  14. HTML学习感悟
  15. Silverlight实用窍门系列:68.Silverlight的资源字典ResourceDictionary
  16. SQL语句——重复记录
  17. (4)进程---daemon守护线程和join阻塞
  18. ARM中的汇编指令
  19. POJ 1011 Sticks(dfs+剪枝)
  20. 深入理解C指针----学习笔记

热门文章

  1. 关于CUDA两种API:Runtime API 和 Driver API
  2. mt-datetime-picker type=&quot;date&quot; 时间格式 bug
  3. 数据结构与算法——AVL树类的C++实现
  4. viewpager 跳转到指定页面
  5. 轻松搞定RabbitMQ(一)——RabbitMQ基础知识+HelloWorld
  6. vs2010中添加dll文件
  7. C递归算法与栈的分析,非全然二叉树遍历分析---ShinePans
  8. 关于CSS和CSS3的布局小知识(干货)
  9. 使用 sigaction 函数实现可靠信号
  10. Android-可随意拖动的View