Cod sursa(job #819764)

Utilizator costel93FMI - Dumea Eduard Constantin costel93 Data 19 noiembrie 2012 18:03:37
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <stdio.h>
#include<string.h>
#define mod1 666001
#define mod2 100007

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 * 73 + v[i] ) % mod1;
		nrv2 = ( nrv2 * 73 + v[i] ) % mod2;
		
		nrs1 = ( nrs1 * 73 + s[i] ) % mod1;
		nrs2 = ( nrs2 * 73 + s[i] ) % mod2;
		
		if(i)
		{
			p1 = ( p1 * 73 ) % mod1;
			p2 = ( p2 * 73 ) % mod2;
		}
		
	}
	
	if( nrv1 == nrs1 &&   nrv2 == nrs2)
		poz[++npoz] = 0;
	
	for(i = lv; i < ls; i++)
	{
		nrs1 = ( ( nrs1 - ( s[i-lv] * p1 ) % mod1 ) * 73 + s[i] ) % mod1;
		nrs2 = ( ( nrs2 - ( s[i-lv] * p2 ) % mod2 ) * 73 + s[i] ) % mod2;
		
		if( nrv1 == nrs1 &&   nrv2 == nrs2)
			poz[++npoz] = i - lv + 1;
	}
	
	fprintf(g, "%d\n", npoz);
	
	for( i = 1; i <= npoz && i<=1000; i++ )
		fprintf(g, "%d ", poz[i]);
	
	return 0;
}