Cod sursa(job #723627)

Utilizator valiro21Valentin Rosca valiro21 Data 25 martie 2012 18:18:28
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 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,i,j;
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,lg1-1,s2);
	obj_Hash=make_Hash(0,lg1-1,s1);
	for(i=1;s2[i-1]==s2[i];i++);
	for(j=1;s1[j-1]==s1[j];j++);

	if(i==lg2 && j==lg1 && s1[0]==s2[0]) {
		printf("%d\n",lg2-lg1);
		for(long i=0;i<=999;i++)
			printf("%d ",i);
	}
	else {
		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("%d\n",nr);
		for(long i=0;i<ve.size();i++)
			printf("%d ",ve[i]);
		printf("\n");
	}

	return 0;
}