Description：

给定两个字符串 $S$ 和 $T$ ，求 $T$ 在 $S$ 中出现了几次，以及分别在哪些位置出现。 $T$ 中 $'?'$ 字符可以匹配任何字符。

$1\leqslant n\leqslant 10^5$

Solution：

把 $S$ 看成一个多项式 $a$ ， $T$ 也看成一个多项式 $b$ （长为 $m$ ）， $'?'$ 的位置是 $0$ ，那么有一个神奇的操作就是用 $FFT$ 匹配。

具体的做法是由于 $S=T$ ，那么他们可以在 $p$ 处匹配等价于： $$ \sum_{i=0}^{m-1}(a[p+i]-b[i])^2\times b[i]=0 $$ 后面那个 $\times b[i]$ 是用来解决 $'?'$ 的

由于 $FFT$ 是用来求卷积的，一般形式为： $$ c[k]=\sum_{i=0}^ka[i]\times b[k-i] $$ 因此我们把 $b$ 翻转，记为 $b'$ ，那么上面那个式子就变成了： $$ \sum_{i=0}^{m-1}(a[p+i]-b'[m-1-i])^2\times b'[m-1-i]=0 $$

这样就成了一个卷积的形式，那么整理后我们就可以构造多项式 $c$ ： $$ \begin{align} c[k]&=\sum_{i=0}^k(a[k-i]-b'[i])^2\times b'[i]\\ &=\sum_{i=0}^k(a[k-i]^2-2\times a[k-i]\times b'[i]+b'[i]^2)\times b'[i]\\ &=\sum_{i=0}^k(a[k-i]^2\times b'[i])-2\times \sum_{i=0}^k(a[k-i]\times b'[i]^2)+\sum_{i=0}^kb'[i]^3 \end{align} $$

前两个都是卷积，可以用 $FFT$ 求解，最后一个就是一个三次幂的前缀和，最后 $c[k]$ 为 $0$ 的位置就是匹配位置。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 400010

char s[MAXN],t[MAXN];

struct comp

{

	double r,i;

	comp(double r_ = 0.0,double i_ = 0.0){r = r_;i = i_;}

}a[MAXN],b[MAXN],c[MAXN];

comp operator + (comp a,comp b){return (comp){a.r + b.r,a.i + b.i};}

comp operator - (comp a,comp b){return (comp){a.r - b.r,a.i - b.i};}

comp operator * (comp a,comp b){return (comp){a.r * b.r - a.i * b.i,a.r * b.i + a.i * b.r};}

int rev[MAXN];

const double PI = acos(-1);

void FFT(comp f[],int l,int type)

{

	for(int i = 0;i < l;++i)

	{

		if(i < rev[i])swap(f[i],f[rev[i]]);

	}

	for(int i = 2;i <= l;i = i << 1)

	{

		comp wn = (comp){cos(-type * 2 * PI / i),sin(-type * 2 * PI / i)};

		for(int j = 0;j < l;j += i)

		{

			comp w = (comp){1,0};

			for(int k = j;k < j + i / 2;++k)

			{

				comp u = f[k],t = w * f[k + i / 2];

				f[k] = u + t;

				f[k + i / 2] = u - t;

				w = w * wn;

			}

		}

	}

	if(type == -1)

	{

		for(int i = 0;i < l;++i)f[i].r /= l;

	}

	return;

}

vector<int> ans;

int main()

{

	scanf("%s",s);n = strlen(s);

	scanf("%s",t);m = strlen(t);

	for(int i = 0,j = m - 1;i < j;++i,--j)swap(t[i],t[j]);

	for(int i = 0;i < m;++i)if(t[i] == '?')t[i] = 0;

	int l = 0,len = 1;

	for(;len <= n + m;len = len << 1,++l);

	for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	//1

	for(int i = 0;i < n;++i)a[i].r = s[i] * s[i];

	for(int i = 0;i < m;++i)b[i].r = t[i];

	FFT(a,len,1);FFT(b,len,1);

	for(int i = 0;i < len;++i)c[i] = c[i] + a[i] * b[i];

	//2

	for(int i = 0;i < len;++i)a[i].r = s[i],a[i].i = 0.0;

	for(int i = 0;i < len;++i)b[i].r = t[i] * t[i],b[i].i = 0.0;

	FFT(a,len,1);FFT(b,len,1);

	for(int i = 0;i < len;++i)c[i] = c[i] - 2 * a[i] * b[i];

	//3

	for(int i = 0;i < len;++i)a[i].r = 1,a[i].i = 0.0;

	for(int i = 0;i < len;++i)b[i].r = t[i] * t[i] * t[i],b[i].i = 0.0;

	FFT(a,len,1);FFT(b,len,1);

	for(int i = 0;i < len;++i)c[i] = c[i] + a[i] * b[i];

	FFT(c,len,-1);

	for(int i = m - 1;i < n;++i)

	{

		if(int(c[i].r + 0.5) == 0)ans.push_back(i - m + 1);

	}

	cout << ans.size() << endl;

	for(int i = 0;i < ans.size();++i)printf("%d\n",ans[i]);

	return 0;

}