Matching

input/code.cpp: In function 'int main()':
input/code.cpp:75:22: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[404040]' [-Wformat=]
  scanf("%s%s", &p, &s);
                      ^
input/code.cpp:75:22: warning: format '%s' expects argument of type 'char*', but argument 3 has type 'char (*)[404040]' [-Wformat=]
input/code.cpp:75:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s%s", &p, &s);
                       ^

#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[404040];

char p[404040];
char s[404040];

int main(){
	scanf("%s%s", &p, &s);
	int psize=strlen(p);
	int ssize=strlen(s);
	int q=0;
	for (int i=0;i<psize;i++) {
		if (p[i]=='?') q++;
	}
	int chs=0;
	int vs=ssize-psize+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<psize;i++){
			if (p[i]==ch) ck.push_back(i);
		}
		if ((ll)ck.size()*(ll)okk.size()<5e7){
			chs+=(int)ck.size();
			for (int o:okk){
				for (int c:ck){
					if (c+o>=ssize) break;
					if (s[c+o]==ch){
						ma[o]++;
					}
				}
			}
			ch++;
		}
		else{
			int as=psize;
			int bs=ssize;
			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<psize;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<ssize;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=psize-1;i<ssize;i++){
				ma[i-psize+1]+=r.F[i]+r.S[i];
			}
			ch+=2;
		}
	}
	vector<int> v;
	for (int i=0;i<ssize-psize+1;i++){
		if (ma[i]==psize-q) v.push_back(i+1);
	}
	printf("%d\n", (int)v.size());
	for (int vv:v){
		printf("%d\n", vv);
	}
}

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