Cod sursa(job #629534)

Utilizator Anamaria20Cotirlea Anamaria Anamaria20 Data 3 noiembrie 2011 14:31:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <cstdio>
#include <string.h>

#define P 173
#define P1 191

#define M 666013
#define M1 193939

FILE *f,*s;

int NA,NB;

int i,j,k,k1,l,m,n;

char A[2000005],B[2000005];

int v1[2000005];

int hasha,hashb,hasha1,hashb1;

int Compara(int a, int b)
{
	for(int j=a;j<=a+b-1;j++)
		if((int)A[j-a]!=(int)B[j]) return 0;
	
	return 1;
}

int main()
{
	f=fopen("strmatch.in","r");
	s=fopen("strmatch.out","w");
	
	fscanf(f,"%s\n%s",A,B);
	
	NA=strlen(A);
	NB=strlen(B);
	
	if(NA>NB)
	{
		fprintf(s,"0");
		
		return 0;
	}
	
	k=1;
	k1=1;
	for(i=0;i<NA;i++)
	{	
		hasha=(hasha*P+(int)A[i])%M;
		
		hasha1=(hasha1*P1+(int)A[i])%M1;
		
		if(i>0)
		{	
			k*=P;
			k%=M;
			
			k1*=P1;
			k1%=M1;
		}	
	}
	
	for(i=0;i<NA;i++)
	{
		hashb=(hashb*P+(int)B[i])%M;
		hashb1=(hashb1*P1+(int)B[i])%M1;
	}
	
	if(hasha==hashb && hasha1==hashb1/*Compara(0,NA)==*/)
		v1[++v1[0]]=0;
	
	for(i=1;i<=NB-NA;i++)
	{
		hashb = (hashb - ((int)B[i-1]*k) % M);
		if (hashb < 0) {
			hashb += M;
		}
		hashb*=P;
		hashb+=(int)B[i+NA-1];
		hashb%=M;
		
		hashb1 = (hashb1 - ((int)B[i-1]*k1) % M1);
		if (hashb1 < 0) {
			hashb1 += M1;
		}
		hashb1*=P1;
		hashb1+=(int)B[i+NA-1];
		hashb1%=M1;
		
		if(hasha==hashb && hasha1==hashb1/*Compara(i,NA)==1*/)
			v1[++v1[0]]=i;
	}	
	
	fprintf(s,"%d\n",v1[0]);
	
	for(i=1;i<=v1[0] &&i<=1000;i++)
		fprintf(s,"%d ",v1[i]);
	
	fclose (s);
	
	return 0;
}