bzoj4259
2024-08-29 10:10:24
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 ;
}
最新文章
- Android导包导致java.lang.NoClassDefFoundError
- mac rvm升级ruby
- 检测Java程序运行时间的2种方法(高精度的时间[纳秒]与低精度的时间[毫秒])
- 串 &; 容斥原理
- IOS开发之代码之九宫格
- Java 比较两张图片的相似度
- 微软控制台带来的PHP控制台输出问题
- Waterfall———瀑布流布局插件, 类似于 Pinterest、花瓣、发现啦。
- mws文件中的tab文件改为相对路径
- Retrofit网络请求库应用01
- hihocoder1388 Periodic Signal
- 【Linux】 Linux权限管理与特殊权限
- IP地址类型
- HTML学习感悟
- Silverlight实用窍门系列:68.Silverlight的资源字典ResourceDictionary
- SQL语句——重复记录
- (4)进程---daemon守护线程和join阻塞
- ARM中的汇编指令
- POJ 1011 Sticks(dfs+剪枝)
- 深入理解C指针----学习笔记
热门文章
- 关于CUDA两种API:Runtime API 和 Driver API
- mt-datetime-picker type=";date"; 时间格式 bug
- 数据结构与算法——AVL树类的C++实现
- viewpager 跳转到指定页面
- 轻松搞定RabbitMQ(一)——RabbitMQ基础知识+HelloWorld
- vs2010中添加dll文件
- C递归算法与栈的分析,非全然二叉树遍历分析---ShinePans
- 关于CSS和CSS3的布局小知识(干货)
- 使用 sigaction 函数实现可靠信号
- Android-可随意拖动的View