Cod sursa(job #332348)

Utilizator AnDrEwBoYA Andrei AnDrEwBoY Data 17 iulie 2009 15:42:12
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<stdio.h>
#include<string.h>

#define MAX_N 2000010
#define base 256
#define NR 100075
#define h(x) x % NR


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

unsigned int hashPattern,hashSubstr,H;
int i;

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


int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	
	scanf("%s",P);
	scanf("%s",T);
	
	n = strlen(T);	
	m = strlen(P); 	 
	
	
	if(m > n) { printf("0\n"); return 0; }
	H = 1;  

	for(i = 0; i < m; i++)        
	{
		hashPattern = h(base * hashPattern + P[i]);
		hashSubstr  = h(base * hashSubstr  + T[i]);
		H = H * base;
	}
	
	for(i = 0; i <= n-m+1; 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]);
	}	
	printf("%d\n",total);
	for(i = 0; i < (total > 1000 ? 1000 : total); i++)
		printf("%d ",sol[i]);
	
	fclose(stdin); fclose(stdout);
	return 0;
}