Cod sursa(job #332109)

Utilizator AnDrEwBoYA Andrei AnDrEwBoY Data 16 iulie 2009 17:02:08
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include<stdio.h>
#include<string>

#define MAX_N 2000000
#define base 256
#define NR 100023
#define h(x) x % NR

char T[MAX_N],P[MAX_N];
int sol[1001];
int n,m,total;

void read(),show(),solve();

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



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

unsigned long long int putere(int d,int m)
{
	int i;
	unsigned long long int p = 1;
	for(i = 1; i <= m; i++) p = h(p*d); 
	return p;	
}

int egal(int k)
{
	int i;
	for(i = 0; i < m; i++)
		if(P[i] != T[k+i]) return 0;
	return 1;
}

void solve()
{
	unsigned long long int hashPattern,hashSubstr,H;
	int i;
	if(m > n) return;
	H = h(putere(base,m-1));
	hashPattern = hashSubstr = 0;
	for(i = 0; i < m; i++)        
	{
		hashPattern = h(base * hashPattern + P[i]);
		hashSubstr  = h(base * hashSubstr  + T[i]);
	}

	for(i = 0; i <= n-m; i++)
	{

		if(hashSubstr == hashPattern) //am gasit patternul
		{ 
			if(egal(i)) //ne asiguram ca nu avem coliziune
			{
				if(total < 1000) 
				{
					sol[total++] = i;
				}
				else
				{
					total++;
				}
			}
		}
		
		hashSubstr = h(base * (hashSubstr - H * 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]);
}