Cod sursa(job #443132)

Utilizator nandoLicker Nandor nando Data 16 aprilie 2010 08:06:54
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 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[MAXM],nm=0;

inline int pow(int64 a,int64 p,int64 mod){
	int64 x=a,r=1;
	while(p){
		if(p&1){
			r=(r*x)%mod;
		}
		x=(x*x)%mod,p>>=1;
	}
	return (int)r;
}

bool rabinKarp(){
	if(m>n){
		return 0;
	}else{
		int h1=pow(SIGMA,m-1,MOD1);
		int h2=pow(SIGMA,m-1,MOD2);

		unsigned p1=0,p2=0,t1=0,t2=0;

		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;

		}
		for(int s=0;s<=n-m;s++){
			if(p1==t1&&p2==t2){
				nm++;
				if(nm<=MAXM){
					match[nm-1]=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(){
	
	fscanf(fin,"%s %s",b,a);
	n=strlen(a),m=strlen(b);

	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;
}