Cod sursa(job #1227715)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 11 septembrie 2014 14:41:56
Problema Potrivirea sirurilor Scor 28
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <cstring>
#define DIM 4000050

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char A[DIM], B[DIM];

int Z[DIM], Sol[DIM>>1];

int sol;

int main() {
	f >> A;
	f >> B;
	int m = strlen(A);
	strcat(A, B);
	strcpy(B, A);
	strcpy(A + 1, B);
	int L = 0, R = 0;
	int n = strlen(A + 1);
	for (int i = 2; i <= n; ++i) {
		if (i > R) {
			Z[i] = 1;
			while (i + Z[i] - 1 <= n && A[i + Z[i] - 1] == A[Z[i]])
				++Z[i];
			--Z[i];
			L = i;
			R = i + Z[i] - 1;
		}
		else {
			int ii = i - L + 1;
			if (Z[ii] < R - i + 1)
				Z[i] = Z[ii];
			else {
				Z[i] = R - i + 1;
				while (i + Z[i] - 1 <= n && A[i + Z[i] - 1] == A[Z[i]])
					++Z[i];
				--Z[i];
				R = i + Z[i] - 1;
				L = i;
			}
		}
	}
	for (int i = m+1; i <= n; ++i)
	if (Z[i] == m) {
		++sol;
		Sol[sol] = i - m - 1;
		if (sol == 1000)
			break;
	}
	g << sol << "\n";
	for (int i = 1; i <= sol; ++i)
		g << Sol[i] << " ";
	return 0;
}