Cod sursa(job #1075807)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 9 ianuarie 2014 16:29:24
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<fstream>
#include<cstring>
#define dim 2000003
#define mod1 2007
#define mod2 2021
#define b 103
using namespace std;
 
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[dim],B[dim];
int i,j,n,m,sol,cnt,sir[1040];
long long ha1,ha2,hb1,hb2,p1,p2;
int main () {
 
    f>>(A+1);
    f>>(B+1);
 
   
    n=strlen(A+1);
    m=strlen(B+1);
	
	if(n>m){
		g<<0;
		return 0;
	}
	
    p1=p2=1;
	ha1=ha2=0;
	
	for(i=1;i<=n;++i){
		ha1=(ha1*b+A[i])%mod1;
		ha2=(ha2*b+A[i])%mod2;
		if(i!=1){
			p1=(p1*b)%mod1;
			p2=(p2*b)%mod2;
		}
	}
	hb1=hb2=0;
	for(i=1;i<=n;++i){
		hb1=(hb1*b+B[i])%mod1;
		hb2=(hb2*b+B[i])%mod2;
		
	}
	if(ha1==hb1 && hb2==ha2){
		sir[1]=1;
		cnt=1;
	}
	for(i=n+1;i<=m;++i){
		hb1=(((hb1-(B[i-n])*p1)%mod1+mod1)*b+B[i])%mod1;
		hb2=(((hb2-(B[i-n])*p2)%mod2+mod2)*b+B[i])%mod2;
		
		if(ha1==hb1 && hb2==ha2){
			sir[++cnt]=i-n;
		}
	}
	
	if(cnt>1000)
		g<<1000;
	else
		g<<cnt;
	
	g<<"\n";
	
	for(i=1;i<=cnt && cnt<=1000;++i)
		g<<sir[i]<<" ";
	
    return 0;
}