Cod sursa(job #1482866)

Utilizator BodStfBodoarca Stefan BodStf Data 8 septembrie 2015 10:44:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<stdio.h>
#include<string.h>

#define MAX 2000001
#define d 256
int count;
int poz[MAX];
char pat[MAX],txt[MAX];

void search(char* pat,char* txt,int q /*nr prim*/)
{
	int M=strlen(pat);
	int N=strlen(txt);
	int i,j,p=0 /*hash-ul pt pattern*/,t=0 /*hash-ul pt txt*/,h=1;

	for(i=0;i<M-1;i++)
		h=(h*d)%q;

	for(i=0;i<M;i++)
	{
		p=(p*d+pat[i])%q;
		t=(t*d+txt[i])%q;
	}

	for(i=0;i<=N-M;i++)
	{
		if(p==t)
		{
			for(j=0;j<M;j++)
				if(txt[i+j]!=pat[j])
					break;
			if(j==M)
			{
				poz[count]=i;
				count++;
			}
		}

		if(i<N-M)
		{
			t=(d*(t-txt[i]*h)+txt[i+M])%q;
			if(t<0)
				t=t+q;
		}
	}
}

int main()
{
	FILE* f1,*f2;
	f1=fopen("strmatch.in","r");
	f2=fopen("strmatch.out","w");
	fscanf(f1,"%s %s",pat,txt);
	search(pat,txt,101);
	fprintf(f2,"%d\n",count);
	for(int i=0;i<count;i++)
		fprintf(f2,"%d ",poz[i]);
	fcloseall();
	return 0;
}