Cod sursa(job #1076067)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 9 ianuarie 2014 20:59:50
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<fstream>
#include<cstring>
#define dim 2000003
#define mod1 100007
#define mod2 100021
#define b 83
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];
int ha1,ha2,hb1,hb2,p1,p2;
int main () {
  
    f>>(A);
    f>>(B);
  
    
    n=strlen(A);
    m=strlen(B);
     
    if(n>m){
        g<<0;
        return 0;
    }
     
    p1=p2=1;
    ha1=ha2=0;
     
    for(i=0;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=0;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;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+1;
        }
    }
     
    if(cnt>1000)
        g<<1000;
    else
        g<<cnt;
     
    g<<"\n";
     
    for(i=1;i<=cnt ;++i){
        g<<sir[i]<<" ";
        if(cnt==1000){
            break;
        }
    }

    return 0;
}