Cod sursa(job #1014336)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 22 octombrie 2013 15:46:32
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <cstdio>
#include <cstring>
using namespace std;
FILE *f=fopen("strmatch.in","r");
FILE *g=fopen("strmatch.out","w");
long long DA,DB,p1,p2;
char A[2000010],B[2000010];
bool poz[2000010];

long long mod1=300337,P=83;
long long mod2=200521;

long long cod1,cod2,codA1,codA2,nr;

int main(void){
    register int i,j;

    fscanf(f,"%s %s",&A,&B);

    DA=strlen(A),DB=strlen(B);

    if(DA>DB){
        fprintf(g,"0");
        return 0;
    }

    //asociem codurile sirului A
    p1=p2=1;
    for(i=0;i<DA;i++){
        codA1=(codA1*P+A[i])%mod1;
        codA2=(codA2*P+A[i])%mod2;
        if(i!=0){
            p1=(p1*P)%mod1;
            p2=(p2*P)%mod2;
        }
    }

    //verificam primele DA elem din sirul B
    for(i=0;i<DA;i++){
        cod1=(cod1*P+B[i])%mod1;
        cod2=(cod2*P+B[i])%mod2;
    }

    if(cod1==codA1 && cod2==codA2)
        nr++,poz[0]=true;

    for(i=DA;i<DB;i++){
        cod1=((cod1-(B[i-DA]*p1)%mod1+mod1)*P+B[i]+mod1)%mod1;
        cod2=((cod2-(B[i-DA]*p2)%mod2+mod2)*P+B[i]+mod2)%mod2;
        if(cod1==codA1 && cod2==codA2)
            nr++,poz[i-DA+1]=true;
    }

    fprintf(g,"%lld\n",nr);
    nr=0;
    for(i=0;i<DB && nr<1000;i++)
        if(poz[i])
            fprintf(f,"%d ",i),nr++;
    fclose(f);
    fclose(g);
    return 0;
}