Leimasin

input/code.cpp: In function 'std::vector<int> f(int, std::__cxx11::string)':
input/code.cpp:28:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (cnt==x.size()) return {};
      ~~~^~~~~~~~~~
input/code.cpp: In function 'void hsh(std::__cxx11::string)':
input/code.cpp:3:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, a, b) for (int i=a; i<(b); i++)
                                     ^
input/code.cpp:90:2: note: in expansion of macro 'FOR'
  FOR(i,1,x.size()) {
  ^~~

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define IO ios_base::sync_with_stdio(0); cin.tie(0)
#define ff first
#define ss second
#define pb push_back
#define INF 2147483647
#define LINF (1LL<<61LL)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define N 1003

string s, L;
int n, m;

void fail() {
	cout<<"-1\n"; exit(0);
}

vector<int> f(int offset, string x) {
	if (x.size()==0) return {};
	int cnt = 0;
	for(char c:x) if(c=='?')cnt++;
	if (cnt==x.size()) return {};
	
	// ...??
	// or
	// ??...
	
	int sz = x.size();
	int idx = -1;
	FOR(i,0,sz-m+1) {
		if (i==0 && x[0]=='?') continue;
		bool found = true;
		FOR(j,0,m) {
			if (x[i+j] == '?') continue;
			if (x[i+j] != L[j]) {found=false; break;}
		}
		if (found) {
			idx = i;
			break;
		}
	}
	
	if (idx == -1) fail();
	
	FOR(j,0,m) x[idx+j] = '?';
	//cout<<x<<" "<<sz<<" offset: "<<offset<<" idx: "<<idx<<"\n";
	
	
	// Go left
	vector<int> left = f(offset+0, x.substr(0,idx+m));
	vector<int> right = f(offset+idx, x.substr(idx,string::npos));
	vector<int> res;
	for (int v:left) res.pb(v);
	for (int v:right) res.pb(v);
	res.pb(idx+offset);
	return res;
}

ll A = 911382323, B = 972663749;
ll pA[N];
ll H[N], HASH[N];
ll pre[N], suff[N];
vector<int> pres;
vector<int> sufs;
vector<int> full;

// 0-indexed
ll rq(int a, int b) {
	if (a == 0) return H[b];
	ll h = (H[b]-H[a-1]*pA[b-a+1])%B;
	if (h<0) h+=B;
	return h;
}

ll ran(int a, int b) {
	if (a==0) return HASH[b];
	ll h = (HASH[b]-HASH[a-1]*pA[b-a+1])%B;
	if (h<0) h+=B;
	return h;
}

void hsh(string x) {
	HASH[0] = x[0];
	FOR(i,1,x.size()) {
		HASH[i] = (HASH[i-1]*A+x[i])%B;
	}
	FOR(l,0,m) {
		ll a = ran(0, l);
		ll b = ran(m-1-l,m-1);
		if (a < 0) a += B;
		if (b < 0) b += B;
		pre[l+1] = a;
		suff[l+1] = b;
	}
}

ll pure(const string& x) {
	ll h = 0;
	for (char c:x) h=(h*A+(ll)c)%B;
	return h;
}

string w = "";
void paint(int p) {
	FOR(j,0,m) w[j+p] = L[j]; 
}

int main() {
	IO;
	cin>>s; cin>>L;
	n = s.size();
	m = L.size();
	FOR(j,0,n) w+="?";
	
	pA[0] = 1;
	H[0] = s[0];
	FOR(i,1,n+1) {
		H[i] = (H[i-1]*A+s[i])%B;
		pA[i] = pA[i-1]*A%B;
	}
	
	hsh(L);
	int i = 0;
	for (;i<n;) {
		// Find block length!
		bool found = false;
		for (int l=m; l>0; l--) {
			if (i+l-1 >= n) continue;
			ll slice = rq(i,i+l-1);
			//cout<<"slice: ("<<i<<","<<i+l-1<<")\n";
			
			if (slice == pre[l]) {
				if (i+m-1 < n) {
					if (l!=m) pres.pb(i+1);
					else full.pb(i+1);
					//cout<<"flip on "<<i+1<<"\n";
					i += l;
					found = true;
					break;
				}
			}
			if (slice == suff[l]) {
				int p = i+l-1;
				if (p-m+1 >= 0) {
					int crd = i-(m-l)+1;
					if (l!=m) sufs.pb(crd);
					else full.pb(crd);
					//cout<<"flip on "<<crd<<"\n";
					i += l;
					found = true;
					break;
				}
			}
		}
		
		if (found) continue;
		// not found :(
		cout<<-1<<"\n";
		exit(0);
	}
	
	//cout<<pres.size()+full.size()+sufs.size()<<"\n";
	
	
	vector<int> res;
	reverse(sufs.begin(), sufs.end());
	for (int pr : pres) res.pb(pr-1);
	for (int sf : sufs) res.pb(sf-1);
	for (int f : full) res.pb(f-1);
	
	for (int v : res) paint(v);
	if (w != s) {
		// Let's ask for confirmation
		FOR(j,0,n) w[j] = '?';
		vector<int> conf = f(0, s);
		for (int v : conf) paint(v);
		if (w == s) {
			// we we're wrong!
			cout<<conf.size()<<"\n";
			for (int v : conf) cout<<v+1<<" ";
			exit(0);
		} else {
			// we we're right
			cout<<"-1\n"; exit(0);
		}
	}
	
	cout<<pres.size()+full.size()+sufs.size()<<"\n";
	reverse(sufs.begin(), sufs.end());
	for (int pr : pres) cout<<pr<<" ";
	for (int sf : sufs) cout<<sf<<" ";
	for (int f : full) cout<<f<<" ";
	
	//cout<<w<<"\n";
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: WRONG ANSWER

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 1

Verdict: ACCEPTED

Test 7

Group: 1

Verdict: ACCEPTED

Test 8

Group: 1

Verdict: ACCEPTED

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 1

Verdict: ACCEPTED

Test 12

Group: 1

Verdict: ACCEPTED

Test 13

Group: 1

Verdict: ACCEPTED

Test 14

Group: 1

Verdict: ACCEPTED

Test 15

Group: 2

Verdict: ACCEPTED

Test 16

Group: 2

Verdict: WRONG ANSWER

Test 17

Group: 2

Verdict: WRONG ANSWER

Test 18

Group: 2

Verdict: ACCEPTED

Test 19

Group: 2

Verdict: ACCEPTED

Test 20

Group: 2

Verdict: ACCEPTED

Test 21

Group: 2

Verdict: WRONG ANSWER

Test 22

Group: 2

Verdict: ACCEPTED

Test 23

Group: 2

Verdict: ACCEPTED

Test 24

Group: 2

Verdict: ACCEPTED

Test 25

Group: 2

Verdict: ACCEPTED

Test 26

Group: 2

Verdict: ACCEPTED

Test 27

Group: 2

Verdict: ACCEPTED

Test 28

Group: 2

Verdict: ACCEPTED

Test 29

Group: 3

Verdict: ACCEPTED

Test 30

Group: 3

Verdict: ACCEPTED

Test 31

Group: 3

Verdict: ACCEPTED

Test 32

Group: 3

Verdict: ACCEPTED

Test 33

Group: 3

Verdict: ACCEPTED

Test 34

Group: 3

Verdict: ACCEPTED

Test 35

Group: 3

Verdict: WRONG ANSWER

Test 36

Group: 3

Verdict: WRONG ANSWER

Test 37

Group: 3

Verdict: ACCEPTED

Test 38

Group: 3

Verdict: ACCEPTED

Test 39

Group: 3

Verdict: ACCEPTED

Test 40

Group: 3

Verdict: ACCEPTED

Test 41

Group: 3

Verdict: ACCEPTED

Test 42

Group: 3

Verdict: ACCEPTED