Cod sursa(job #629475)

Utilizator Anamaria20Cotirlea Anamaria Anamaria20 Data 3 noiembrie 2011 13:54:41
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <string.h>

#define P 173
#define M 666013

FILE *f,*s;

int NA,NB;

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

char A[2000005],B[2000005];

int A1[2000005],B1[2000005];

int v1[2000005];

int hasha,hashb;

int Compara(int a, int b)
{
	for(int j=a;j<=a+b-1;j++)
		if(A1[j-a]!=B1[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;
	for(i=0;i<NA;i++)
	{	
		A1[i]=(int)A[i];
		
		hasha=(hasha*P+A1[i])%M;
		
		if(i>0)
		{	
			k*=P;
			k%=M;
		}	
	}
	
	for(i=0;i<NB;i++)
		B1[i]=(int)B[i];
	
	for(i=0;i<NA;i++)
		hashb=(hashb*P+B1[i])%M;
	
	//printf("%d %d\n",hasha,hashb);
	
	if(hasha==hashb && Compara(0,NA)==1)
		v1[++v1[0]]=1;
	
	for(i=1;i<=NB-NA;i++)
	{
		//hashb-=((B1[i-1]*k)%M)+P;
		hashb = (hashb - B1[i-1]*k) % M;
		if (hashb < 0) {
			hashb += M;
		}
		hashb*=P;
		hashb+=B1[i+NA-1];
		hashb%=M;
		
		if(hasha==hashb && Compara(i,NA)==1)
			v1[++v1[0]]=i;
	}	
	
	fprintf(s,"%d\n",v1[0]);
	
	for(i=1;i<=v1[0];i++)
		fprintf(s,"%d ",v1[i]);
	
	fclose (s);
	
	return 0;
}