Cod sursa(job #820202)

Utilizator mariacMaria Constantin mariac Data 20 noiembrie 2012 13:17:48
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<cstdio>
#include<string.h>
#define mod 666013
#define mod2 100107
using namespace std;


char A[2000001], B[2000001];
int poz[1002];
int main()
{	
	int s1,s2,s21,s22,n=0,pf,pf2,i;
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s %s",A,B);
	
	s1=0;s2=0;
	pf=1;pf2=1;
	s21=0;s22=0;
	for(i=0;i<strlen(A);i++)
		{
			s1=( s1*75 + (A[i]-'0') )%mod;
	    
			s2=( s2*75 + (A[i]-'0') )%mod2;
			s21=( s21*75 +(B[i]-'0') )%mod;
	    
			s22=( s22*75 + (B[i]-'0') )%mod2;
		
		
			if(i){
					pf=(pf*75)%mod;
					pf2=(pf2*75)%mod2;
				 }
		}
	
	if(s21==s1&&s22==s2)
		{
			n++;
			poz[n]=0;
		}
	for(i=strlen(A);i<strlen(B);i++)
		{
			s21=( ( s21 - ( B [ i - strlen(A) ] - '0' ) * pf % mod + mod ) * 75 + (B[i] - '0') ) % mod;
			s22=( ( s22 - ( B [ i - strlen(A) ] - '0' ) * pf2 % mod2 + mod2 ) * 75  + (B[i] - '0') ) % mod2;
			if( s21==s1 && s22==s2 )
				if(n<1000) poz[++n]=i-strlen(A)+1;
					 else n++;
		}
	
	printf("%d\n",n);
	
	
	for(i=1;i<=n&&i<=1000;i++)
		printf("%d ",poz[i]);
	
	return 0;
}