Cod sursa(job #443136)

Utilizator nandoLicker Nandor nando Data 16 aprilie 2010 08:19:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <cstdio>
#include <cstring>
using namespace std;

FILE* fin=fopen("strmatch.in","r");
FILE* fout=fopen("strmatch.out","w");

#define MAX 2000005
#define MAXM 1000
#define SIGMA 128
#define MOD1 100007
#define MOD2 100021

typedef unsigned long long int64;

char a[MAX],b[MAX];
int n,m,match[MAX],nm=0;

bool rabinKarp(){
	if(m>n){
		return 0;
	}else{
		unsigned p1=0,p2=0,t1=0,t2=0,h1=1,h2=1;

		for(int i=0;i<m;i++){
			p1=(SIGMA*p1+b[i])%MOD1;
			p2=(SIGMA*p2+b[i])%MOD2;

			t1=(SIGMA*t1+a[i])%MOD1;
			t2=(SIGMA*t2+a[i])%MOD2;

			if(i!=0){
				h1=(h1*SIGMA)%MOD1;
				h2=(h2*SIGMA)%MOD2;
			}
		}

		for(int s=0;s<=n-m;s++){
			if(p1==t1&&p2==t2){
				match[nm++]=s;
			}
			if(s<n-m){
				t1=((t1-(a[s]*h1)%MOD1+MOD1)*SIGMA+a[s+m])%MOD1;
				t2=((t2-(a[s]*h2)%MOD2+MOD2)*SIGMA+a[s+m])%MOD2;
			}
		}
		return 1;
	}
}

int main(){
	
	fgets(b,MAX,fin);
	fgets(a,MAX,fin);
	n=strlen(a)-1,m=strlen(b)-1;

	if(rabinKarp()){
		fprintf(fout,"%d\n",nm);
		nm=(nm>MAXM)?MAXM:nm;
		for(int i=0;i<nm;i++){
			fprintf(fout,"%d ",match[i]);
		}
		fputc('\n',fout);
	}else{
		fprintf(fout,"0\n");
	}

	fclose(fin);
	fclose(fout);
	return 0;
}