Cod sursa(job #819716)

Utilizator costel93FMI - Dumea Eduard Constantin costel93 Data 19 noiembrie 2012 17:13:16
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <stdio.h>
#include<string.h>
#define mod1 666001
#define mod2 102341

using namespace std;
FILE *f=fopen("strmatch.in","r"), *g=fopen("strmatch.out","w");

char s[2000001], v[2000001];
int i, j, nrv1=0, nrs1=0, nrv2=0, nrs2=0, p1=1, p2=1, lv, ls, poz[2000001], npoz=0;

int main()
{
	
	fscanf(f, "%s%s", &v, &s);
	
	lv=strlen(v);
	ls=strlen(s);
	
	for(i=0;i<lv;i++)
	{
		nrv1=(nrv1*256+v[i])%mod1;
		nrv2=(nrv2*256+v[i])%mod2;
		
		nrs1=(nrs1*256+s[i])%mod1;
		nrs2=(nrs2*256+s[i])%mod2;
		
		if(i)
			p1=(p1*256)%mod1;
			p2=(p2*256)%mod2;
		
	}
	
	for(i=lv; i<ls && npoz<=1000; i++)
	{
		if(nrv1==nrs1&&nrv2==nrs2)
			poz[++npoz]=i-lv;
		
		nrs1=(((nrs1-(s[i-lv]*p1)%mod1+mod1)*256)+s[i])%mod1;
		nrs2=(((nrs2-(s[i-lv]*p2)%mod2+mod2)*256)+s[i])%mod2;
	}
	
	fprintf(g, "%d\n", npoz);
	
	for(i=1;i<=npoz;i++)
		fprintf(g, "%d ", poz[i]);
	
	return 0;
}