Cod sursa(job #2447701)

Utilizator Alex18maiAlex Enache Alex18mai Data 14 august 2019 12:49:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
//ALEX ENACHE

#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>

using namespace std;

//-----------------------------------------------------------------

#include <fstream>

//ifstream cin("input"); ofstream cout("output");
ifstream cin("strmatch.in"); ofstream cout("strmatch.out");

int z[4000100];
vector < int > ans;

int main() {

	string a, b, s;
	cin >> a >> b;

	cin >> a >> b;
	s = '#' + a + '#' + b;

	int cont = 0;
	int R = 0, C = 0;

	for (int i = 2; i < s.size(); i++) {
		z[i] = max(min(z[i - C + 1], R - i), 0);

		while (s[z[i] + 1] == s[i + z[i]]) {
			z[i]++;
		}

		if (R < i + z[i] - 1) {
			R = i + z[i] - 1;
			C = i;
		}

		if (z[i] == a.size()) {
			cont++;
			if (ans.size() < 1000) {
				ans.push_back(i - a.size() - 2);
			}
		}
	}

	cout << cont << '\n';
	for (auto& x : ans) {
		cout << x << " ";
	}

	return 0;
}