Cod sursa(job #695980)

Utilizator DSzprogDombi Szabolcs DSzprog Data 28 februarie 2012 16:04:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstring>
#include <cstdio>
#include <cmath>

const int mx = 2000002;

int n;
int m;
char a[mx];
char b[mx];

int k[mx];
void create() {
	for (int i = 1; i < n; ++i) {
		int p = k[i - 1];
		if (a[i] == a[p]) {
			k[i] = p + 1;
		} else {
			k[i] = 0;
		}
	}
}

int num;
int s[1000];

int main() {
	FILE * in = fopen("strmatch.in", "rt");
	FILE * out = fopen("strmatch.out", "wt");

	n = strlen(fgets(a, mx, in)) - 1;
	m = strlen(fgets(b, mx, in)) - 1;

	create();
	for (int i = 0; i < n; ++i) {
		printf("%c %d\n", a[i], k[i]);
	}

	for (int i = 0, j = 0; j < m; ++i, ++j) {
		if (b[j] == a[i]) {
		} else if (k[i] && b[j] == a[k[i] - 1]) {
			i = k[i] - 1;
		} else {
			i = 0;
		}
		if (i == n - 1) {
			i = k[i] - 1;
			if (num < 1000) {
				s[num] = j - n + 1;
			}
			++num;
		}
	}

	fprintf(out, "%d\n", num);
	for (int i = 0; i < num; ++i) {
		fprintf(out, "%d ", s[i]);
	}

	fclose(in);
	fclose(out);
}