Cod sursa(job #489125)

Utilizator elmercerAlex Mercer elmercer Data 1 octombrie 2010 10:59:44
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <stdio.h>
#include <string.h>
#define MOD 67867979 	

long i, val, val2, len1, len2, gpow, sol, v[2000010];
char s1[2000010], s2[2000010];

long put(long num) {
	long p = 1; 
	
	for (long i = 1; i <= num; ++i) {
		p *= 26;
		if (p > MOD)
			p %= MOD;
	}
	
	return p;
}

int main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	scanf("%s\n%s", s1, s2);
	
	len1 = strlen(s1);
	
	for (i = 0; i < len1; ++i) {
		val += put(len1 - i - 1) * (long)(s1[i] - 'A');
		val2 += put(len1 - i - 1) * (long)(s2[i] - 'A');
		if (val > MOD) val %= MOD;
		if (val2 > MOD) val2 %= MOD;
	}
	gpow = put(len1 - 1);
	if (val == val2) {
		++sol;
		v[sol] = 0;
	}
	
	len2 = strlen(s2);
	
	for (i = 0; i + len1 <= len2; ++i) {
		val2 -= ((gpow * (long)(s2[i] - 'A')) % MOD);
		val2 *= 26;
		val2 += (long)(s2[i + len1] - 'A');
		if (val == val2) {
			++sol;
			v[sol] = i + 1;
		}
	}
	
	printf("%ld\n", sol);
	for (i = 1; i <= sol && i <= 1000; ++i) {
		printf("%ld ", v[i]);
	}
	printf("\n");
	//printf("%ld %ld\n", val, val2);
	
	return 0;
}