Matching

#include <bits/stdc++.h>
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(co{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;
}
vector<ll> conv(vector<ll> a, vector<ll> b){
	int as=a.size(), bs=b.size();
	int n=1;
	while (n<as+bs-1) n*=2;
	vector<co> aa(n*2), bb(n*2);
	for (int i=0;i<as;i++) aa[i]=a[i];
	for (int i=0;i<bs;i++) bb[i]=b[i];
	aa=fft(aa, 1);bb=fft(bb, 1);
	vector<co> c(2*n);
	for (int i=0;i<2*n;i++) c[i]=aa[i]*bb[i];
	c=fft(c, -1);
	c.resize(as+bs-1);
	vector<ll> r(as+bs-1);
	for (int i=0;i<as+bs-1;i++) r[i]=(ll)round(c[i].real());
	return r;
}

int chv[30];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string p,s;
	cin>>p>>s;
	for (int i=0;i<30;i++){
		chv[i]=rand()%100000;
	}
	ll ev=0;
	vector<ll> pv;
	for (int i=0;i<(int)p.size();i++){
		if (p[i]=='?') pv.push_back(0);
		else {
			int aa=rand()%100000;
			pv.push_back(aa);
			ev+=(ll)aa*(ll)chv[p[i]-'a'];
		}
	}
	vector<ll> sv;
	for (int i=0;i<(int)s.size();i++){
		sv.push_back(chv[s[i]-'a']);
	}
	reverse(pv.begin(), pv.end());
	auto r=conv(pv, sv);
	vector<int> v;
	for (int i=(int)p.size()-1;i<(int)s.size();i++){
		if (r[i]==ev) v.push_back(i-(int)p.size()+2);
	}
	cout<<v.size()<<'\n';
	for (int vv:v){
		cout<<vv<<'\n';
	}
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: WRONG ANSWER