记录编号	247223	评测结果	AAAAAAAAAA
题目名称	[BZOJ 4503] 你猜是不是KMP	最终得分	100
用户昵称	_Horizon	是否通过	通过
代码语言	C++	运行时间	6.018 s
提交时间	2016-04-08 11:14:24	内存使用	27.32 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define maxn 300010
using namespace std;

struct cpx{
	double r, i;
	cpx(double a = 0, double b = 0):r(a), i(b){}
	cpx operator+(const cpx& o)const{return cpx(r+o.r, i+o.i);}
	cpx operator-(const cpx& o)const{return cpx(r-o.r, i-o.i);}
	cpx operator*(const cpx& o)const{return cpx(r*o.r-i*o.i, r*o.i+i*o.r);}
	cpx operator/(const double& k)const{return cpx(r/k, i/k);}
}P[maxn], A[maxn], B[maxn], C[maxn], D[maxn];
int r[maxn], l;
int rev(int S){
	int ret = 0;
	for(int i = 0; i < l; i ++){
		ret = ret << 1 | (S & 1);
		S >>= 1;
	}return ret;
}

const double pi = acos(-1.0);

void FFT(cpx A[], int n, int t){
	for(int i = 0; i < n; i ++) P[r[i]] = A[i];
	for(int i = 0; i < n; i ++) A[i] = P[i];
	for(int k = 2; k <= n; k <<= 1){
		cpx wn = cpx(cos(2*pi/k), t*sin(2*pi/k));
		for(int i = 0; i < n; i += k){
			cpx w = cpx(1, 0);
			for(int j = 0; j < k>>1; j ++){
				cpx T = w * A[i+j+(k>>1)];
				A[i+j+(k>>1)] = A[i+j] - T;
				A[i+j] = A[i+j] + T;
				w = w * wn;
			}
		}
	}
	if(t == -1)
	    for(int i = 0; i < n; i ++)
	        A[i] = A[i] / n;
}

char s[maxn];

int a[maxn], b[maxn], amt, ans[maxn];

const double eps = 1e-5;
int Filter(double x){return x < eps && x > -eps;}

long long sum;
double Q[maxn];

int main(){
	freopen("guess.in", "r", stdin);
	freopen("guess.out", "w", stdout);
	scanf("%s", s);
	int n1 = strlen(s);
	for(int i = 0; i < n1; i ++)
	    a[i] = s[i] - 'a' + 1;
	scanf("%s", s);
	int n2 = strlen(s);
	for(int i = 0; i < n2; i ++){
		if(s[i] == '?')	b[n2-i-1] = 0;
		else b[n2-i-1] = s[i] - 'a' + 1;
	}

	for(int i = 0; i < n2; i ++)
		sum += (long long)b[i] * b[i] * b[i];

	int m1 = n1 + n2, n = 1; l = 0;
	for(; n <= m1; n <<= 1, l ++);
	for(int i = 1; i < n; i ++)r[i] = rev(i);

	for(int i = 0; i < n1; i ++)A[i].r = (double)a[i] * a[i];
	for(int i = 0; i < n2; i ++)B[i].r = b[i];
	FFT(A, n, 1), FFT(B, n, 1);
	for(int i = 0; i < n; i ++) C[i] = A[i] * B[i];
	FFT(C, n, -1);

	memset(A, 0, sizeof A);
	memset(B, 0, sizeof B);
	for(int i = 0; i < n1; i ++)A[i].r = a[i];
	for(int i = 0; i < n2; i ++)B[i].r = (double)b[i] * b[i];
    FFT(A, n, 1), FFT(B, n, 1);
	for(int i = 0; i < n; i ++) D[i] = A[i] * B[i];
	FFT(D, n, -1);
	//for(int i = 0; i < n; i ++)printf("%.3lf ", C[i].r);puts("");

	for(int i = 0; i < n; i ++)
		Q[i] = C[i].r - 2 * D[i].r + sum;

	for(int i = 0; i+n2-1 < n1; i ++)
		if(Filter(Q[i+n2-1]))
		    ans[++ amt] = i;
	printf("%d\n", amt);
	for(int i = 1; i <= amt; i ++)
		printf("%d\n", ans[i]);
	return 0;
}

/*
Input
ababcadaca
a?a
Output
3
0
5
7
*/