Cod sursa(job #570790)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 3 aprilie 2011 16:41:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include<cstdio>
#include<cstring>
#include<vector>

#define Lmax 2000010
#define theymatch hashB1 == hashA1 && hashB2 == hashA2
#define P 73
#define M1 100007
#define M2 100021

using namespace std;

int lung_a,lung_b,hashA1,hashA2,hashB1,hashB2,P1,P2;

vector <int> sol;

char a[Lmax],b[Lmax];
bool isletter(const char &x){
	
	if(x>='A' && x<='Z')
		return 1;
return 0;
}

int main(){
		
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	
	fgets(a,Lmax,stdin);
	fgets(b,Lmax,stdin);
	
	if(!isletter(a[strlen(a)-1]))
		a[strlen(a)-1]='\0';
	
	if(!isletter(b[strlen(b)-1]))
		b[strlen(b)-1]='\0';
	
	lung_a=strlen(a);
	lung_b=strlen(b);
	
	P1=P2=1;
	hashA1 = hashA2 = 0;
	
	for(int i=0 ; i<lung_a; ++i){
		
		hashA1 = 	(hashA1 * P + a[i] ) % M1;
		hashA2 = 	(hashA2 * P + a[i] ) % M2;
		
		if(i!=0){
			P1 = (P1 * P) %M1;
			P2 = (P2 * P) %M2;
		}
	}
	
	if( lung_b < lung_a)
	{ printf("0");
	  return 0;
	}
	
	hashB1 = hashB2 = 0;
	
	for(int i=0 ; i<lung_a; ++i)		
		hashB1 = 	(hashB1 * P + b[i] ) % M1,
		hashB2 = 	(hashB2 * P + b[i] ) % M2;
		
	if(theymatch)
		sol.push_back(0);
	
	for(int i=lung_a; i<lung_b;++i ){
		
		// hasul curent = cel anterior minus prima litera + litera curenta
		hashB1 = ((hashB1 - (b[i-lung_a] * P1) %M1 + M1) * P + b[i]) %M1;
		hashB2 = ((hashB2 - (b[i-lung_a] * P2) %M2 + M2) * P + b[i]) %M2;
		
		if(theymatch)
			sol.push_back(i-lung_a+1);
	}
		
	printf("%d\n",sol.size());
	for(vector<int>::iterator it=sol.begin();it!=sol.end();++it)
		printf("%d ",*it);
		
return 0;
}