Cod sursa(job #723653)

Utilizator valiro21Valentin Rosca valiro21 Data 25 martie 2012 18:33:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 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,minn;
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);
	if(obj_Hash == Hash)
		for(i=1;s2[i-1]==s2[i];i++);

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