Cod sursa(job #332102)

Utilizator AnDrEwBoYA Andrei AnDrEwBoY Data 16 iulie 2009 16:50:50
Problema Potrivirea sirurilor Scor 40
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","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);
	 
}

unsigned long long int putere(int d,int m)
{
	int i;
	unsigned long long int p = 1;
	for(i = 1; i <= m; i++) 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]);
}