P4173 残缺的字符串

文本串为$A\left(长度为n\right)A(长度为n)$A(长度为n)，模式串为$B\left(长度为m\right)B(长度为m)$B(长度为m)

不考虑通配符的时候，可以用完全匹配函数可以是$P\left(x\right)={\sum }_{i=0}^{m-1}\left[B\right(i)-A(x-m+1+i){]}^2\{P(x)=\backslash sum\_\{i=0\}^\{m-1\}\{[B(i)-A(x-m+1+i)\backslash \; ]^2\}\}$P(x)=∑i=0m−1​[B(i)−A(x−m+1+i) ]2

将通配符赋值为$00$0，那么有完全匹配函数$P\left(x\right)={\sum }_{i=0}^{m-1}\left[B\right(i)-A(x-m+1+i){]}^2\ast A(x-m+1+i)\ast B(i)\{P(x)=\backslash sum\_\{i=0\}^\{m-1\}\{[B(i)-A(x-m+1+i)\backslash \; ]^2*A(x-m+1+i)*B(i)\}\}$P(x)=∑i=0m−1​[B(i)−A(x−m+1+i) ]2∗A(x−m+1+i)∗B(i)

老套路：$S\left(i\right)=B(m-1-i),B\left(i\right)=S(m-1-i)S(i)=B(m-1-i),B(i)=S(m-1-i)$S(i)=B(m−1−i),B(i)=S(m−1−i)

那么有完全匹配函数$P\left(x\right)={\sum }_{i=0}^{m-1}S(m-1-i{)}^3\ast A(x-m+1+i)+{\sum }_{i=0}^{m-1}A(x-m+1+i{)}^3\ast S(m-1-i)-2\ast {\sum }_{i=0}^{m-1}A(x-m+1+i{)}^2\ast S(m-1-i{)}^2\{P(x)=\backslash sum\_\{i=0\}^\{m-1\}\{S(m-1-i)^3*A(x-m+1+i)\}+\backslash sum\_\{i=0\}^\{m-1\}\{A(x-m+1+i)^3*S(m-1-i)\}-2*\backslash sum\_\{i=0\}^\{m-1\}\{A(x-m+1+i)^2*S(m-1-i)^2\}\}$P(x)=∑i=0m−1​S(m−1−i)3∗A(x−m+1+i)+∑i=0m−1​A(x−m+1+i)3∗S(m−1−i)−2∗∑i=0m−1​A(x−m+1+i)2∗S(m−1−i)2

$P\left(x\right)={\sum }_{i+j=x}S(i{)}^3\ast A(j)+{\sum }_{i+j=x}A(i{)}^3\ast S(j)-2\ast {\sum }_{i+j=x}A(i{)}^2\ast S(j{)}^2\{P(x)=\backslash sum\_\{i+j=x\}\{S(i)^3*A(j)\}+\backslash sum\_\{i+j=x\}\{A(i)^3*S(j)\}-2*\backslash sum\_\{i+j=x\}\{A(i)^2*S(j)^2\}\}$P(x)=∑i+j=x​S(i)3∗A(j)+∑i+j=x​A(i)3∗S(j)−2∗∑i+j=x​A(i)2∗S(j)2

做7次$FFTFFT$FFT就好了，浮点数精度可能会有问题，p(x)<1就可以看作$00$0了，我看有的人是p(x)<1e−7，而我改成p(x)<1e−6都wa。

用$NTTNTT$NTT涉及取余（$p\left(x\right)p(x)$p(x)会大于$mod\left(998244353\right)mod(998244353)$mod(998244353)），可能会影响结果？我试了一下只有65分。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(1<<20)+7;
const double PI=acos(-1.0);
struct Complex{
	double x,y;
	Complex(double _x=0.0,double _y=0.0) {
		x=_x;
		y=_y;
	}
	Complex operator-(const Complex &b) const {
		return Complex(x-b.x,y-b.y);
	}
	Complex operator+(const Complex &b) const {
		return Complex(x+b.x,y+b.y);
	}
	Complex operator*(const Complex &b) const {
		return Complex(x*b.x-y*b.y,x*b.y+y*b.x);
	}
};
int r[maxn];
inline void fft(Complex *y,int len,int opt) {
	for(int i=0;i<len;++i)
		if(i<r[i]) swap(y[i],y[r[i]]);
	for(int h=2;h<=len;h<<=1) {
		Complex wn(cos(2*PI/h),sin(opt*2*PI/h));
		for(int j=0;j<len;j+=h) {
			Complex w(1,0);
			for(int k=j;k<j+h/2;++k) {
				Complex tmp=w*y[k+h/2];
				y[k+h/2]=y[k]-tmp;
				y[k]=y[k]+tmp;
				w=w*wn;
			}
		}
	}
	if(opt==-1) {
		for(int i=0;i<len;++i) y[i].x/=len;
	}
}
Complex A[maxn],B[maxn],p[maxn];
double x[maxn],y[maxn];
char a[maxn/2],b[maxn/2];
int main() {
	int n,m,k,lim(1);
	scanf("%d%d",&m,&n);
	scanf("%s%s",b,a);
	while(lim<(n<<1)) lim<<=1;
	for(int i=0; i<lim; ++i) r[i]=(i&1)*(lim>>1)+(r[i>>1] >> 1);
	for(int i=0;i<n;++i) x[i]=(a[i]!='*')?a[i]-'a'+1:0,A[i]=Complex(x[i]*x[i]*x[i],0);
	for(int i=0;i<m;++i) y[i]=(b[m-1-i]!='*')?b[m-1-i]-'a'+1:0,B[i]=Complex(y[i],0);
	fft(A,lim,1),fft(B,lim,1);
	for(int i=0;i<lim;++i) {
		p[i]=p[i]+A[i]*B[i];
		A[i]=Complex(x[i],0);
		B[i]=Complex(y[i]*y[i]*y[i],0);
	}
	fft(A,lim,1),fft(B,lim,1);
	for(int i=0;i<lim;++i) {
		p[i]=p[i]+A[i]*B[i];
		A[i]=Complex(x[i]*x[i],0);
		B[i]=Complex(y[i]*y[i],0);
	}
	fft(A,lim,1),fft(B,lim,1);
	for(int i=0;i<lim;++i) p[i]=p[i]-A[i]*B[i]*Complex(2,0);
	fft(p,lim,-1);
	vector<int>ans;
	for(int i=m-1;i<n;++i) {
		if(fabs(p[i].x)<1) ans.emplace_back(i-m+2);
	}
	cout<<ans.size()<<'\n';
	for(int i:ans) cout<<i<<' ';
	return 0;
}