Cod sursa(job #397303)

Utilizator ConsstantinTabacu Raul Consstantin Data 16 februarie 2010 19:40:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<stdio.h>
#define P 73
#define P2 111
#include<string.h>
#include<vector>
using namespace std;
char a[ 2000010 ],b[ 2000010 ];
unsigned int i,j,k,ha1,ha2,h1,h2,na,nb,p1,p2,nr,x;
vector<int>sol;
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);

scanf("%s %s",a,b);
na = strlen(a);
nb = strlen(b);
p1 = p2 = 1;
for(i = 0 ; i < na;i++)
	{ha1 = ha1*P + a[i];
	ha2 = ha2*P2 + a[i];
	
	if(i != 0)
		{p1 = p1*P;
		 p2 = p2*P2;
		}
	}
	
if(na > nb){printf("0");return 0;}

for(i = 0 ; i < na;i++)
	{h1 = h1*P + b[i];
	h2 = h2*P2 + b[i];
	}
if(h1 == ha1 && h2 == ha2)
	{nr++;sol.push_back(0);}
	
for(i = na;i < nb ; i++)
	{x = b[i - na];
	h1 = ((h1 - x*p1 )*P + b[i]);
	h2 = ((h2 - x*p2)*P2 + b[i]);
	
	if(h1 == ha1 && h2 == ha2)
		{nr++;
		if(nr < 1000)
		sol.push_back(i-na+1);
		}
	}
	
printf("%d\n",nr);

for(i = 0;i < nr ; i++)
	printf("%d ",sol[i]);

return 0;}