显示代码纯文本
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const double Pi = acos(-1);
const int maxn = (1<<18)+5;
struct Complex {
double x, y;
explicit Complex(double x=0.0, double y=0.0) : x(x), y(y) {}
Complex operator + (const Complex& a) { return Complex(x+a.x, y+a.y); }
Complex operator - (const Complex& a) { return Complex(x-a.x, y-a.y); }
Complex operator * (const Complex& a) { return Complex(x*a.x-y*a.y, x*a.y+y*a.x); }
Complex operator * (const double& a) { return Complex(x*a, y*a); }
};
Complex a[maxn], b[maxn], c[maxn], W[maxn][2];
int rev[maxn];
void FFT_Init(int n) {
int l = 0; while((1<<l)<n) ++l; --l;
for(int i=0; i<n; ++i) {
W[i][0] = Complex(cos(2*Pi*i/n), sin(2*Pi*i/n));
W[i][1] = Complex(cos(-2*Pi*i/n), sin(-2*Pi*i/n));
if(i) rev[i] = rev[i>>1]>>1|((i&1)<<l);
}
}
void FFT(Complex *a, int n, int op) {
for(int i=0; i<n; ++i) if(rev[i]>i) swap(a[rev[i]], a[i]);
for(int k=2; k<=n; k<<=1)
for(int j=0; j<n; j+=k)
for(int i=0; i<(k>>1); ++i) {
Complex t = a[i+j+(k>>1)]*W[n/k*i][op];
a[i+j+(k>>1)] = a[i+j]-t;
a[i+j] = a[i+j]+t;
}
if(op) {
double inv = 1.0/n;
for(int i=0; i<n; ++i) a[i] = a[i]*inv;
}
}
char s1[maxn], s2[maxn];
int n1, n2, ans[maxn];
int main() {
freopen("guess.in","r",stdin);freopen("guess.out","w",stdout);
scanf("%s%s", s1, s2);
n1 = strlen(s1);
n2 = strlen(s2); reverse(s2, s2+n2);
for(int i=0; i<n1; ++i) s1[i] = s1[i]=='?' ? 0 : s1[i]-'a'+1;
for(int i=0; i<n2; ++i) s2[i] = s2[i]=='?' ? 0 : s2[i]-'a'+1;
int n = 1; while(n<n1+n2-1) n <<= 1;
FFT_Init(n);
for(int i=0; i<n; ++i) a[i] = Complex(s1[i]*s1[i]);
for(int i=0; i<n; ++i) b[i] = Complex(s2[i]);
//for(int i=0;i<n;i++)printf("%.2f ",a[i].x);putchar(10);
//for(int i=0;i<n;i++)printf("%.2f ",b[i].x);putchar(10);
FFT(a, n, 0); FFT(b, n, 0);
for(int i=0; i<n; ++i) c[i] = a[i]*b[i];
//for(int i=0;i<n;i++)printf("%.2f ",c[i].x);putchar(10);
//for(int i=0;i<n;i++)printf("%.2f ",c[i].y);putchar(10);
//memset(a, 0, sizeof a);memset(b, 0, sizeof b);
for(int i=0; i<n; ++i) a[i] = Complex(s1[i]);
for(int i=0; i<n; ++i) b[i] = Complex(s2[i]*s2[i]);
//for(int i=0;i<n;i++)printf("%.2f ",a[i].x);putchar(10);
//for(int i=0;i<n;i++)printf("%.2f ",b[i].x);putchar(10);
FFT(a, n, 0); FFT(b, n, 0);
for(int i=0; i<n; ++i) c[i] = c[i]-a[i]*b[i]*2.0;
//for(int i=0;i<n;i++)printf("%.2f ",c[i].x);putchar(10);
//for(int i=0;i<n;i++)printf("%.2f ",c[i].y);putchar(10);
FFT(c, n, 1);
//for(int i=0;i<n;i++)printf("%.2f ",c[i].x);putchar(10);
//for(int i=0;i<n;i++)printf("%.2f ",c[i].y);putchar(10);
int t = 0;
for(int i=0; i<n2; ++i) t += (int)s2[i]*s2[i]*s2[i];
//printf("t3=%d\n",t);
int cnt = 0;
for(int i=n2-1; i<n1; ++i) if(t+round(c[i].x)==0) ++cnt;
printf("%d\n", cnt);
for(int i=n2-1; i<n1; ++i) if(t+round(c[i].x)==0) printf("%d\n", i-n2+1);
return 0;
}
_Itachi