Cod sursa(job #489130)

Utilizator elmercerAlex Mercer elmercer Data 1 octombrie 2010 11:44:35
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <stdio.h>
#include <string.h>
#define MOD 32103109 	

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 *= 62;
		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;
}
void fa(char  *a, int len)
{
	for( int i = 0; i < len; ++i)
	{
		if ('0' <= a[i] && a[i] <= '9') a[ i ] -='0';
		if ('a' <= a[i] && a[i] <= 'z') a[ i ] -='a' - 10;
		if ('A' <= a[i] && a[i] <= 'Z') a[ i ] -='A' - 36;

	}		
}

int main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	scanf("%s\n%s", s1, s2);
	
	len1 = strlen(s1);
	len2 = strlen(s2);
	fa( s1 , strlen(s1));
	fa( s2 , strlen(s2));
	
	
	for (i = 0; i < len1; ++i) {
		val = val * 62 + s1[ i ];
		val2 = val2 * 62 + s2[ i ];
		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);
		}
	}
	

	
	for (i = 0; i + len1 < len2; ++i) {
		
		val2 -= (gpow * s2[i])  % MOD;
		if( val2 < 0) val2 += MOD;
		val2 *= 62;
		val2 += s2[ i + len1 ];
		val2 %= MOD;
		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;
}