Cod sursa(job #723607)

Utilizator valiro21Valentin Rosca valiro21 Data 25 martie 2012 17:55:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <cstdio>
#include <cstring>
#include <vector>
#define CMax 2000021

using namespace std;

char s1[CMax],s2[CMax];
int lg1,lg2,n,k,Hash,obj_Hash,nr;
vector<int> ve;

int make_Hash(long lo,long hi,char s[]) {
	int Hash=0;
	//Hash code
	for(long i=lo;i<=hi;i++)
		Hash+=s[i]-65;
	return Hash;
}

int remake_Hash(int Hash,char c1,char c2) {
	//Hash code
	Hash-=c1-c2;
	return Hash;
}

int main() {
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);

	scanf("%s %s",s1,s2);
	lg1=strlen(s1);
	lg2=strlen(s2);
	Hash=make_Hash(0,lg2-1,s2);
	obj_Hash=make_Hash(0,lg1-1,s1);
	while(k+lg1<=lg2) {
		if(Hash=obj_Hash)
			if(!strncmp(s1,s2+k,lg1)) {
				nr++;
				if(nr<=1000)
					ve.push_back(k);
			}
		Hash=remake_Hash(Hash,s2[k],s2[k+lg1]);
		k++;
	}

	printf("%ld\n",nr);
	for(long i=0;i<ve.size();i++)
		printf("%ld ",ve[i]);
	printf("\n");
	return 0;
}