Cod sursa(job #332210)

Utilizator AnDrEwBoYA Andrei AnDrEwBoY Data 16 iulie 2009 23:50:52
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include<stdio.h>
#include<string.h>

#define MAX_N 2000010
#define base 71
#define NR 100075
#define h(x) x % NR
#define h1(x) x % (NR-52)

int sol[1001];
int n,m,total;
char P[MAX_N],T[MAX_N];
void read(),show(),solve();

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	
	read();
   	solve();
	show();
	
	fclose(stdin); fclose(stdout);
	return 0;
}



void read()
{
	scanf("%s",P);
	scanf("%s",T);
	
	n = strlen(T);	
	m = strlen(P); 	 
}

void solve()
{
	unsigned long long int hashPattern,hashSubstr,hashPattern1,hashSubstr1,H,H1;
	int i;
	if(m > n) return; 
	H = H1 = 0;  
	hashPattern = hashSubstr = hashPattern1 = hashSubstr1 = 0;
	for(i = 0; i < m; i++)        
	{
		hashPattern  = h(base * hashPattern + P[i]);
		hashSubstr   = h(base * hashSubstr  + T[i]);
		
		hashPattern1 = h1(base * hashPattern1 + P[i]);
		hashSubstr1  = h1(base * hashSubstr1  + T[i]);
		
		H  = H * base;
		H1 = H1 * base; 
	}
	
	for(i = 0; i <= n-m+1; i++)
	{
		if(hashSubstr == hashPattern && hashSubstr1 == hashPattern1) //am gasit patternul
		{ 
				if(total < 1000) 
				{
					sol[total++] = i;
				}
				else
				{
					total++;
				}
		}
		
		hashSubstr = h(base * (hashSubstr - H * T[i]) + T[i+m]);
		hashSubstr1 = h1(base * (hashSubstr1 - H1 * T[i]) + T[i+m]);
	}	
}

void show()
{
	printf("%d\n",total);
	for(int i = 0; i < (total > 1000 ? 1000 : total); i++)
		printf("%d ",sol[i]);
}