Leimasin

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:46: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
ll A = 911382323, B = 972663749;
ll pA[N];
ll H[N], HASH[N];
ll pre[N], suff[N];
int n, m;
//vector<int> pres, sufs, full;
vector<int> ch;
 
 
struct Node {
	vector<int> pres, sufs, full;
} MOVE[N];
 
// 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 s, L;
 
// {(a,b), moves to make this segment}
set<pair<pii, int>> vr;
set<pair<pii, int>> vr2;
bool proc[N]; // processed
int pr = 0;
 
string w = "";
void paint(int p) {
	FOR(j,0,m) w[j+p] = L[j]; 
}
 
void solved() {
	/*
	int sz=pres.size()+full.size()+sufs.size();
	reverse(pres.begin(), pres.end());
	reverse(sufs.begin(), sufs.end());
	for (int pr : pres) paint(pr);
	for (int sf : sufs) paint(sf);
	for (int f : full) paint(f);
	
	cout<<sz<<"\n";
	for (int pr : pres) cout<<pr+1<<" ";
	for (int sf : sufs) cout<<sf+1<<" ";
	for (int f : full) cout<<f+1<<" ";*/
	vector<int> seq;
	for (int idx : ch) {
		// check out MOVE[idx]
		Node p = MOVE[idx];
		vector<int> pres = p.pres;
		vector<int> sufs = p.sufs;
		vector<int> full = p.full;
		sort(pres.begin(), pres.end());
		sort(sufs.begin(), sufs.end());
		reverse(sufs.begin(), sufs.end());
		for (int v : pres) seq.pb(v);
		for (int v : sufs) seq.pb(v);
		for (int v : full) seq.pb(v);
	}
	
	cout<<seq.size()<<"\n";
	for(int v:seq)cout<<v+1<<" ";
	//cout<<"worked\n";
	exit(0);
}
 
void addProc(int x) {
	if (!proc[x]) pr++;
	proc[x] = true;
	if (pr == n) solved();
}
 
// inclusive
void process(int a, int b) {
	FOR(j,a,b+1) addProc(j);
}
 
int main() {
	IO;
	cin>>s; cin>>L;
	n = s.size();
	m = L.size();
	
	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;
	}
	
	FOR(j,0,n) w+="?";
	
	hsh(L);
	ll label = pure(L);
	
	// Find all labels
	FOR(i,0,n-m+1) {
		if (proc[i]) continue;
		// Match for label
		if (rq(i,i+m-1) == label) {
			MOVE[i].full.pb(i);
			ch.pb(i);
			vr.insert({{i,i+m-1}, i});
			process(i,i+m-1);
		}
	}
	
	//FOR(i,0,n) cout<<(proc[i]?"1":"0");
	
	while (vr.size()) {
		//makeCompact();
		// Try to spread a segment
		bool ext = false;
		auto seg = *vr.begin();
		int a = seg.ff.ff, b = seg.ff.ss;
		int midx = seg.ss;
		
		// Check for any prefix
		for (int l=m; l>=1; l--) {
			int lp = a-l;
			if (lp < 0) continue;
			if (proc[lp]) continue;
			if (rq(lp,a-1) == pre[l]) {
				//cout<<"found prefix at "<<lp+1<<"\n";
				vr.erase(vr.begin());
				vr.insert({{lp, b}, midx});
				MOVE[midx].pres.pb(lp);
				//pres.pb(lp);
				process(lp, a-1);
				ext = true;
				break;
			}
		}
		
		if (ext) continue;
		
		/*
		// Check for any suffix, as no prefix was found
		for (int l=m; l>=1; l--) {
			int rp = b+l;
			if (rp >= n) continue;
			if (proc[rp]) continue;
			if (rq(b+1,rp) == suff[l]) {
				cout<<"found sefix at "<<rp-m+1+1<<"\n";
				vr.erase(vr.begin());
				vr.insert({{a,rp}, midx});
				MOVE[midx].sufs.pb(rp-m+1);
				process(b+1, rp);
				ext = true;
			}
		}*/
		
		vr2.insert(*vr.begin());
		vr.erase(vr.begin());
	}
	
	while (vr2.size()) {
		// Try to spread a segment
		bool ext = false;
		auto seg = *vr2.begin();
		int a = seg.ff.ff, b = seg.ff.ss;
		int midx = seg.ss;
		
		
		// Check for any suffix
		for (int l=m; l>=1; l--) {
			int rp = b+l;
			if (rp >= n) continue;
			if (proc[rp]) continue;
			if (rq(b+1,rp) == suff[l]) {
				//cout<<"found sefix at "<<rp-m+1+1<<"\n";
				vr2.erase(vr2.begin());
				vr2.insert({{a,rp}, midx});
				MOVE[midx].sufs.pb(rp-m+1);
				process(b+1, rp);
				ext = true;
			}
		}
		
		if (ext) continue;
		vr2.erase(vr2.begin());
	}
	
	cout<<"-1\n";
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

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: WRONG ANSWER

Test 14

Group: 1

Verdict: ACCEPTED

Test 15

Group: 2

Verdict: ACCEPTED

Test 16

Group: 2

Verdict: ACCEPTED

Test 17

Group: 2

Verdict: ACCEPTED

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: WRONG ANSWER

Test 28

Group: 2

Verdict: ACCEPTED

Test 29

Group: 3

Verdict: ACCEPTED

Test 30

Group: 3

Verdict: ACCEPTED

Test 31

Group: 3

Verdict: WRONG ANSWER

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: WRONG ANSWER

Test 42

Group: 3

Verdict: ACCEPTED