传送门
题意简述：给两个字符串s,ts,ts,t，ttt中可能有通配符，问ttt在sss出现的次数和所有位置。
思路：一道很熟悉的题，跟bzoj4259bzoj4259bzoj4259差不多的。
然后把每个字符串的字符投射成数值(′a′'a'′a′ ~ ′z′→1'z'\rightarrow1′z′→1~262626,′?′→0'?'\rightarrow0′?′→0)。
考虑对于两个数(a,b)(a,b)(a,b)设计一个distdistdist函数dista,b=b(a−b)2dist_{a,b}=b(a-b)^2dista,b=b(a−b)2那么
两个等长的字符串S,TS,TS,T的DistDistDist值DistS,T=∑i=0∣S∣−1distSi,TIDist_{S,T}=\sum_{i=0}^{|S|-1}dist_{S_i,T_I}DistS,T=∑i=0∣S∣−1distSi,TI
显然如果DistS,T=0Dist_{S,T}=0DistS,T=0表示S,TS,TS,T可以匹配。
那么考虑把给出的串TTT反过来，这样DistS,TDist_{S,T}DistS,T就变成了卷积的形式，即ci=∑(aj−bi−j)2bi−jc_i=\sum(a_j-b_{i-j})^2b_{i-j}ci=∑(aj−bi−j)2bi−j，由于直接做不是很好做因此我们把这个式子拆开变成：ci=∑aj2bi−j−2ajbi−j2+bi−j3c_i=\sum a_j^2b_{i-j}-2a_jb_{i-j}^2+b_{i-j}^3ci=∑aj2bi−j−2ajbi−j2+bi−j3前面两项用两次fftfftfft搞定，最后一项的加和是一个定值，全部算出来之后加起来就是DistDistDist每一项的值。
时间复杂度O(nlogn)O(nlog_n)O(nlogn)
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=1e5+5;
struct cp{
double x,y;
friend inline cp operator+(const cp&a,const cp&b){return (cp){a.x+b.x,a.y+b.y};}
friend inline cp operator-(const cp&a,const cp&b){return (cp){a.x-b.x,a.y-b.y};}
friend inline cp operator*(const cp&a,const cp&b){return (cp){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
friend inline cp operator/(const cp&a,const double&b){return (cp){a.x/b,a.y/b};}
};
typedef long long ll;
int tim,lim;
vector<int>pos;
vector<cp>A,B;
inline void init(const int&up){
lim=1,tim=0;
while(lim<=up)lim<<=1,++tim;
pos.resize(lim),A.resize(lim),B.resize(lim),pos[0]=0;
for(ri i=0;i<lim;++i)pos[i]=(pos[i>>1]>>1)|((i&1)<<(tim-1));
}
const double pi=acos(-1.0);
inline void fft(vector<cp>&a,const int&type){
for(ri i=0;i<lim;++i)if(i<pos[i])swap(a[i],a[pos[i]]);
for(ri mid=1;mid<lim;mid<<=1){
cp wn=(cp){cos(pi/mid),sin(pi/mid)*type},w,a0,a1;
for(ri j=0,len=mid<<1;j<lim;j+=len){
w=(cp){1,0};
for(ri k=0;k<mid;++k,w=w*wn)a0=a[j+k],a1=a[j+k+mid]*w,a[j+k]=a0+a1,a[j+k+mid]=a0-a1;
}
}
if(type==-1)for(ri i=0;i<lim;++i)a[i]=a[i]/lim;
}
struct poly{
vector<cp>a;
poly(int k=0,cp x=(cp){0,0}){a.resize(k+1),a[k]=x;}
inline cp&operator[](const int&k){return a[k];}
inline const cp&operator[](const int&k)const{return a[k];}
inline int deg()const{return a.size()-1;}
inline poly extend(const int&k){poly ret=*this;return ret.a.resize(k+1),ret;}
friend inline poly operator*(const poly&a,const poly&b){
int n=a.deg(),m=b.deg();
poly ret;
init(n+m);
for(ri i=0;i<=n;++i)A[i]=a[i];
for(ri i=0;i<=m;++i)B[i]=b[i];
for(ri i=n+1;i<lim;++i)A[i]=(cp){0,0};
for(ri i=m+1;i<lim;++i)B[i]=(cp){0,0};
fft(A,1),fft(B,1);
for(ri i=0;i<lim;++i)A[i]=A[i]*B[i];
return fft(A,-1),ret.a=A,ret;
}
};
char s[N],t[N];
int n,m;
ll val[N];
inline void solve1(){
poly a(n),b(m);
for(ri i=0;i<=n;++i)a[i].x=(s[i]-'a'+1)*(s[i]-'a'+1),a[i].y=0;
for(ri i=0;i<=m;++i)b[i].x=t[i]=='?'?0:t[i]-'a'+1,b[i].y=0;
reverse(b.a.begin(),b.a.end());
a=a*b;
for(ri i=0,j=m;j<=n;++i,++j)val[i]+=(ll)(a[j].x+0.5);
}
inline void solve2(){
poly a(n),b(m);
for(ri i=0;i<=n;++i)a[i].x=s[i]-'a'+1,a[i].y=0;
for(ri i=0;i<=m;++i)b[i].x=t[i]=='?'?0:(t[i]-'a'+1)*(t[i]-'a'+1),b[i].y=0;
reverse(b.a.begin(),b.a.end());
a=a*b;
for(ri i=0,j=m;j<=n;++i,++j)val[i]-=(ll)(a[j].x+0.5)*2;
}
inline void solve3(){
ll sum=0;
for(ri i=0,x;i<=m;++i)x=t[i]=='?'?0:t[i]-'a'+1,sum+=(ll)x*x*x;
for(ri i=0,j=m;j<=n;++i,++j)val[i]+=sum;
}
int main(){
scanf("%s%s",s,t),n=strlen(s)-1,m=strlen(t)-1;
solve1(),solve2(),solve3();
vector<int>ans;
for(ri i=0,j=m;j<=n;++i,++j)if(!val[i])ans.push_back(i);
cout<<ans.size()<<'\n';
for(ri i=0;i<ans.size();++i)cout<<ans[i]<<'\n';
return 0;
}