Cod sursa(job #508428)

Utilizator cosmyoPaunel Cosmin cosmyo Data 8 decembrie 2010 11:27:32
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int  P = 1000000000;
const int  N = 2000005;
const int  B = 29;
int x, y, n, val, m;
int  sol[1005],nr;
char  a[N], b[N];

int main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
		
		fgets(a, N, stdin);
		fgets(b, N, stdin);
	    	
		int i, j ,sw, k;
		
		n = strlen( a );--n;
		m = strlen( b );--m;
		for( i = 0;i < n; ++i)
		 	k=a[i]-'A'+1,x =( ( x * B ) % P + k ) % P;
		val = 1;
		for( i = 1;i <= n-1; ++i)
			val = (val * B) % P;
		for( i = 0 ;i < n; ++i)
		   k = b[i] - 'A' + 1,	y = ( (y * B ) % P  + k ) % P;
		b[m]='0';
		for( i = n;i <= m ; ++i) {
			if( x == y ) {
				sw = 1;
				for(j = i-1, k = n - 1;k >=0 ; --k, --j)
					if( b[j] != a[k] ) {
						sw = 0;
						break;
					}
				if( sw ) {
					++nr;
					if(nr <= 1000)
						sol[nr] = i - n;
				}
			}
		  y = ( y + P - val *( b[i - n] - 'A' + 1) ) % P;
		  y = ( ( y * B ) % P + b[i]-'A' + 1 ) % P;
		}
			
		printf("%ld\n" ,nr);
		
		
		for(i = 1;i <=min(nr,1000); ++i)
			printf("%ld ", sol[i]);

	return 0;
}