Cod sursa(job #508675)

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

int main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
		
		scanf("%s %s",&a,&b);
	    	
		 int i, j ,sw, k;
        		
		n = strlen( a );
		m = strlen( b );
	//	while(!( (a[n]>='a'&&a[n]<='z')||(a[n]>='A'&&a[n]<='Z')||(a[n]>='0'&&a[n]<='9') ) ) --n;
    //    while(!( (b[m]>='a'&&b[m]<='z')||(b[m]>='A'&&b[m]<='Z')||(b[m]>='0'&&b[m]<='9') ) ) --m;
      
	
		for( i = 0;i < n; ++i)
		 	x =( ( x * B ) % P + a[i] ) % P;
		val = 1;
		for( i = 1;i <= n-1; ++i)
			val = (val * B) % P;
		for( i = 0 ;i < n; ++i)
		   	y = ( (y * B ) % P  + b[i] ) % 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] ) )% P ) % P;
		  y = ( ( y * B ) % P + b[i] ) % P;
		}
			
		printf("%d\n" ,nr);
		
		
		for(i = 1;i <=min(nr,1000); ++i)
			printf("%d ", sol[i]);

	return 0;
}