Cod sursa(job #1266893)

Utilizator BonCipBonciocat Ciprian Mircea BonCip Data 19 noiembrie 2014 11:29:14
Problema Potrivirea sirurilor Scor 36
Compilator c Status done
Runda Arhiva educationala Marime 1.03 kb
#include <stdio.h>
#include <ctype.h>

#define N_MAX 2000000
#define MOD 1234567891
#define P 666013

char A[N_MAX + 2], B[N_MAX + 2];
int M, N, buff[N_MAX + 1], sp;
unsigned long long checksum, pwr = 1;

void read(FILE *fin)
{
	while (isalnum(A[++M] = fgetc(fin))); // M cu 1 mai mare
	while (isalnum(B[++N] = fgetc(fin))); // N cu 1 mai mare
}

void prec()
{
	int i;
	for (i = 1; i < M; i++) {
		pwr = (pwr * P) % MOD;
		checksum = (checksum * P + A[i]) % MOD;
	}
}

void rk()
{
	int i;
	unsigned long long curr = 0;
	for (i = 1; i < N; i++) {
		if (curr == checksum && sp < 1000) {
			buff[++sp] = i - M;
		}
		curr = (curr * P + B[i] - (i >= M ? B[i - M + 1] * pwr : 0)) % MOD;
	}
}

void print(FILE *fout)
{
	int i;
	fprintf(fout, "%d\n", sp);
	for (i = 1; i <= sp; i++) {
		fprintf(fout, "%d ", buff[i]);
	}
}

int main()
{
	FILE *fin, *fout;
	fin = fopen("strmatch.in", "r");
	fout = fopen("strmatch.out", "w");
	
	read(fin);
	prec();
	rk();
	print(fout);
	
	//printf("%s%d\n%s%d", A + 1, M, B + 1, N);
	
	fclose(fin);
	fclose(fout);
	return 0;
}