题目

有一个长度为 \(m\) 的字符串 \(A\) 和 一个长度为 \(n\) 的字符串 \(B\)，

它们有若干位置为通配符，现在问 \(B\) 的每一个后缀是否存在前缀为 \(A\)。

分析

考虑每次就是问 \(A[m-i]\) 与 \(B[r-i+1]\) 是否相等，把 \(A\) 反转一下，就得到 \(A'[i]\)

然后建立一个匹配函数 \((A[i]-B[j])^2A[i]B[j]\) 一定要乘起来之后都为0，这个后缀才有可能。

然后NTT好像会被卡，所以写了FFT

代码

#include 
#include 
#include 
#include 
#include 
#define rr register
#define mem(f,n) fill(f,f+n,(CP){0,0})
#define cpy(f,g,n) memcpy(f,g,sizeof(CP)*(n))
using namespace std;
const double pi=acos(-1.0);
const int N=2000011; int n,m,len,a[N],b[N],stac[N],TOP;
double Sin[31],Cos[31];
struct CP{
	double x,y;
	inline CP operator +(const CP &t)const{return (CP){x+t.x,y+t.y};}
	inline CP operator -(const CP &t)const{return (CP){x-t.x,y-t.y};}
	inline CP operator *(const CP &t)const{return (CP){x*t.x-y*t.y,x*t.y+y*t.x};}
}ff[N<<2],ans[N<<2];
inline signed iut(){
    rr int ans=0; rr char c=getchar();
    while (!isdigit(c)) c=getchar();
    while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
    return ans;
}
inline void print(int ans){
    if (ans>9) print(ans/10);
    putchar(ans%10+48);
}
namespace Fourier{
	int rev[N<<2],LAST; CP Wt[N<<2],F[N<<2];
	inline void Pro(int n){
		if (LAST==n) return; LAST=n,Wt[0]=(CP){1,0};
		for (rr int i=0;i>1]>>1)|((i&1)?n>>1:0);
	}
	inline void FFT(CP *f,int n,int op){
		Pro(n);
		for (rr int i=0;i