Cod sursa(job #508712)

Utilizator cosmyoPaunel Cosmin cosmyo Data 9 decembrie 2010 15:09:04
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int P1 = 666013;
const int P2 = 1000007;
const int B1 = 3 ;
const int B2 = 5 ;
const int N = 2000007;
char a[N], b[N];
int n, m, val1, val2, sol[1005], nr;
int x, y, r, t;
int main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	int i;
    
	scanf("%s %s", &a, &b);
	
	n = strlen(a);
	m = strlen(b);
	val1 = val2 = 1;
		for( i = 0; i < n; ++i) {
			x = ( x * B1 + a[i] ) % P1;
			r = ( r * B2 + a[i] ) % P2;
			if( i != 0) {

				val1 = ( val1 * B1 ) % P1;
				val2 = ( val2 * B2 ) % P2; 
			}
		}

		for ( i = 0; i < n; ++i ) {
			y = ( y * B1 + b[i] ) % P1;
			t = ( t * B2 + b[i] ) % P2;
		}
        b[m]='0'-1;
		for( i = n; i <= m; ++i) {
			if( x == y && r == t ) {
				++nr;
				if( nr <= 1000 )
					sol[nr] = i - n ;
			}
 		    
			y = ( y -  b[i-n] * val1 ) % P1 + P1; y = ( ( y * B1 ) + b[i] ) % P1 ;
			t = ( t -  b[i-n] * val2 ) % P2 + P2; t = ( ( t * B2 ) + b[i] ) % P2 ;
		}
	 printf("%d\n", nr);
	 	
	 	for( i = 1; i <= min( 1000, nr ); ++i)
			printf("%d ",sol[i]);
	return 0;
}