Cod sursa(job #792608)

Utilizator mihaiSimuSimu Mihai mihaiSimu Data 27 septembrie 2012 22:57:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <stdio.h>
#include <string.h>
#include <vector>
#define p 71
#define mod1 200007
#define mod2 2000021

using namespace std;

char a[2000006],b[2000006];
vector<int> matches;


int main(){
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);	
	scanf("%s",&a);
	scanf("%s",&b);
	
	long h1a=0,h2a=0,h1b=0,h2b=0;
	int lena=strlen(a),lenb=strlen(b);
	long pp1=1,pp2=1;
	for(int i=0;i<lena;i++){
		if(i!=(lena-1)){pp1*=p;pp1%=mod1;
		pp2*=p;pp2%=mod2;
		}
		h1a=(h1a*p+a[i])%mod1;
		h2a=(h2a*p+a[i])%mod2;
		h1b=(h1b*p+b[i])%mod1;
		h2b=(h2b*p+b[i])%mod2;
	}
	if(h1a==h1b && h2a==h2b) matches.push_back(0);
	
	for(int i=1;i<=(lenb-lena);i++){
		h1b=((h1b-(b[i-1]*pp1)%mod1+mod1)*p+b[i+lena-1])%mod1;
		h2b=((h2b-(b[i-1]*pp2)%mod2+mod2)*p+b[i+lena-1])%mod2;
		if(h1a==h1b && h2a==h2b) matches.push_back(i);
	}
	printf("%d\n",matches.size());
	for(int i=0;i<1000 && i<matches.size();i++){
		printf("%d ",matches[i]);
	
	}

	return 0;
}