Cod sursa(job #2190761)

Utilizator RazvanR104Razvan-Andrei Ciocoiu RazvanR104 Data 31 martie 2018 18:16:46
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 4e6 + 10;

int Z[NMAX];
char AB[NMAX];

int main() {
	assert(freopen("strmatch.in", "r", stdin));
	assert(freopen("strmatch.out", "w", stdout));

	cin >> AB;
	int lenA = strlen(AB);
	cin >> (AB + lenA + 1);
	int lenB = strlen(AB + lenA + 1);
	int lenAB = lenA + lenB + 1;

	Z[0] = lenAB;
	int left = -1, right = -1;
	for (int i = 1; i < lenAB; ++i) {
		if (i >= left && i <= right) {
			int matchSize = Z[i - left];
			if (i + matchSize - 1 < right) {
				Z[i] = matchSize;
			} else {
				while (i + matchSize < lenAB && AB[i + matchSize] == AB[matchSize])
					++matchSize;
				Z[i] = matchSize;
				if (i + matchSize - 1 > right) {
					left = i;
					right = i + matchSize - 1;
				}
			}
		} else {
			int matchSize = 0;
			while (i + matchSize < lenAB && AB[i + matchSize] == AB[matchSize])
					++matchSize;
			Z[i] = matchSize;
			left = i;
			right = i + matchSize - 1;
		}
	}

	vector<int> answer;
	for (int i = lenA + 1; i < lenAB && answer.size() < 1000; ++i) {
		if (Z[i] == lenA)
			answer.push_back(i - lenA - 1);
	}

	cout << answer.size() << '\n';
	for (int i: answer)
		cout << i << ' ';
	cout << '\n';

	return 0;
}