Cod sursa(job #2275149)

Utilizator alexandru223Dan Alexandru Dicu alexandru223 Data 2 noiembrie 2018 21:16:22
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = a; i < b; i++)
#define TRvi(c, it) for (vi::iterator it = c.begin(); it != c.end(); it++)
#define TRvii(c, it) for (vii::iterator it = c.begin(); it != c.end(); it++)
#define INF 2000000000

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;

void kmp(string w, string s, vii &known_words) {
	int next_stop = 1e9;
	int w_i = 0;
	bool toggle = 0;
	REP(s_i, 0, s.size()) {
		if (s[s_i] == w[0] && w_i != 0 && !toggle) {
			next_stop = s_i;
			toggle = 1;
		}
		if (w[w_i] == s[s_i]) w_i++;
		else {
			toggle = 0;
			w_i = 0;
			s_i = min(next_stop-1, s_i);
			next_stop = 1e9;
		}
		if (w_i == w.size()) {
			toggle = 0;
			known_words.push_back(make_pair(s_i-w_i+1, s_i));
			w_i = 0;
			s_i = min(next_stop-1, s_i);
			next_stop = 1e9;
		}
	}
}

int main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	string s1, s2;
	cin >> s1 >> s2;
	vii known_words;
	kmp(s1, s2, known_words);
	cout << known_words.size() << '\n';
	TRvii(known_words, it)
		cout << (*it).first << ' ';

	return 0;
}