Matching

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef double ld;
typedef long long ll;
typedef complex<ld> co;
const ld PI=atan2(0, -1);
vector<co> fft(vector<co> x, int d) {
	int n=x.size();
	for (int i=0;i<n;i++) {
		int u=0;
		for (int j=1;j<n;j*=2) {
			u*=2;
			if (i&j) u++;
		}
		if (i<u) swap(x[i], x[u]);
	}
	for (int m=2;m<=n;m*=2) {
		co wm=exp(complex<ld>{0, d*2*PI/m});
		for (int k=0;k<n;k+=m) {
			co w=1;
			for (int j=0;j<m/2;j++) {
				co t=w*x[k+j+m/2];
				co u=x[k+j];
				x[k+j]=u+t;
				x[k+j+m/2]=u-t;
				w*=wm;
			}
		}
	}
	if (d==-1) for (int i=0;i<n;i++) x[i]/=n;
	return x;
}
pair<vector<co>, vector<co> > tfft(vector<co>& a, vector<co>& b, int d) {
	vector<co> fv(a.size());
	for (int i=0;i<(int)a.size();i++) fv[i]=a[i]+co(0, 1)*b[i];
	fv=fft(fv, d);
	vector<co> r1(a.size()), r2(a.size());
	for (int i=0;i<(int)a.size();i++) {
		if (d==-1||i==0||i==(int)a.size()/2) {
			r1[i]=fv[i].X;r2[i]=fv[i].Y;
		} else {
			co t=fv[i]-fv[(int)a.size()-i];
			r1[i]={fv[i].X-t.X/2, t.Y/2};
			r2[i]=(fv[i]-r1[i])*co(0, -1);
		}
	}
	return {r1, r2};
}
pair<vector<ll>, vector<ll>> tconv(int as, int bs, int n, vector<co>& a, vector<co>& b, vector<co>& c, vector<co>& d){
	auto ab=tfft(a, b, 1);
	auto cd=tfft(c, d, 1);
	vector<co> c1(2*n);
	vector<co> c2(2*n);
	for (int i=0;i<2*n;i++) c1[i]=ab.F[i]*ab.S[i];
	for (int i=0;i<2*n;i++) c2[i]=cd.F[i]*cd.S[i];
	auto r=tfft(c1, c2, -1);
	vector<ll> r1(as+bs-1), r2(as+bs-1);
	for (int i=0;i<as+bs-1;i++) {
		r1[i]=(ll)round(r.F[i].X);
		r2[i]=(ll)round(r.S[i].X);
	}
	return {r1, r2};
}

int ma[1010101];

int main(){
	ios_base::sync_with_stdio(0);
	string p,s;
	cin>>p>>s;
	int q=0;
	for (int i=0;i<(int)p.size();i++) {
		if (p[i]=='?') q++;
	}
	int chs=0;
	int vs=(int)s.size()-(int)p.size()+1;
	for (char ch='a';ch<='z';){
		vector<int> okk;
		for (int i=0;i<vs;i++){
			if (ma[i]==chs) okk.push_back(i);
		}
		vector<int> ck;
		for (int i=0;i<(int)p.size();i++){
			if (p[i]==ch) ck.push_back(i);
		}
		if ((ll)ck.size()*(ll)okk.size()<3e7){
			chs+=(int)ck.size();
			for (int o:okk){
				for (int c:ck){
					if (c+o>=(int)s.size()) break;
					if (s[c+o]==ch){
						ma[o]++;
					}
				}
			}
			ch++;
		}
		else{
			int as=p.size();
			int bs=s.size();
			int n=1;
			while (n<as+bs-1) n*=2;
			vector<co> a(n*2), b(n*2), c(n*2), d(n*2);
			for (int i=0;i<(int)p.size();i++){
				if (p[i]==ch) {
					a[as-1-i]=1;
					chs++;
				}
				else if(p[i]==ch+1) {
					c[as-1-i]=1;
					chs++;
				}
			}
			for (int i=0;i<(int)s.size();i++){
				if (s[i]==ch) b[i]=1;
				else if(s[i]==ch+1) d[i]=1;
			}
			auto r=tconv(as, bs, n, a, b, c, d);
			for (int i=(int)p.size()-1;i<(int)s.size();i++){
				ma[i-(int)p.size()+1]+=r.F[i]+r.S[i];
			}
			ch+=2;
		}
	}
	vector<int> v;
	for (int i=0;i<(int)s.size()-(int)p.size()+1;i++){
		if (ma[i]==(int)p.size()-q) v.push_back(i+1);
	}
	cout<<v.size()<<endl;
	for (int vv:v){
		cout<<vv<<" ";
	}
	cout<<endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED