Cod sursa(job #1227718)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 11 septembrie 2014 14:56:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <cstring>
#define minim(a,b) (a>b ? b : a)
#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 (R >= i)
			Z[i] = minim(Z[i - L + 1], R - i + 1);
		for (; i + Z[i] <= n && A[i + Z[i]] == A[1 + Z[i]]; ++Z[i]);
		if (R < i + Z[i] - 1) {
			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;
	}
	g << sol << "\n";
	for (int i = 1; i <= sol && i <= 1000; ++i)
		g << Sol[i] << " ";
	return 0;
}