Cod sursa(job #489127)

Utilizator elmercerAlex Mercer elmercer Data 1 octombrie 2010 11:14:21
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 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;
}

long test(long l1, long l2) {
	long ok = 1;
	
	for (long i = l1; i <= l2; ++i) {
		if (s1[i - l1] != s2[i]) {
			ok = 0;
			break;
		}
	}
	
	return ok;
}

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) {
		if (test(0, len1 - 1)) {
			++sol;
			v[sol] = 0;
		} else {
			while (1);
		}
	}
	
	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) {
			if (test(i + 1, i + len1)) {
				++sol;
				v[sol] = i + 1;
			} else {
				while (1);
			}
		}
	}
	
	printf("%ld\n", sol);
	for (i = 1; i <= sol && i <= 1000; ++i) {
		printf("%ld ", v[i]);
	}
	printf("\n");
	if( sol > 1000) while(1 );
	//printf("%ld %ld\n", val, val2);
	
	return 0;
}