Cod sursa(job #701996)

Utilizator DSzprogDombi Szabolcs DSzprog Data 1 martie 2012 18:56:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 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 if (a[i] == a[0]) {
			k[i] = 1;
		} else {
			k[i] = 0;
		}
	}
}

int num;
int s[1001];

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();

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

	fprintf(out, "%d\n", num);
	int dist = num < 1000 ? num : 1000;
	for (int i = 1; i <= dist; ++i) {
		fprintf(out, "%d ", s[i]);
	}

	fclose(in);
	fclose(out);
}