Cod sursa(job #1014338)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 22 octombrie 2013 15:55:48
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 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];
int poz[1011];

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[nr]=0;

    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[nr]=i-DA+1;
        if(nr>1000)
            break;
    }

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