Cod sursa(job #2418796)

Utilizator CleliaClelia Maria Dobrescu Clelia Data 6 mai 2019 14:19:15
Problema Potrivirea sirurilor Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <cstdio>
#include <cstring>
#define MOD1 666013
#define MOD2 1000003
char a[2000001],b[2000001];
int v[1001];
int main(){
    FILE* fin=fopen("strmatch.in","r");
    FILE* fout=fopen("strmatch.out","w");
    int nra1=0,nra2=0,nrb1=0,nrb2=0,nr=0,n1,n2,i,x1=1,x2=1;
    fscanf (fin,"%s %s",&a,&b);
    n1=strlen(a);
    n2=strlen(b);
    for (i=0;i<n1;i++){
        nra1=(nra1*26+a[i]-'A')%MOD1;
        nra2=(nra2*26+a[i]-'A')%MOD2;
        nrb1=(nrb1*26+b[i]-'A')%MOD1;
        nrb2=(nrb2*26+b[i]-'A')%MOD2;
        if (i){
            x1=(x1*26)%MOD1;
            x2=(x2*26)%MOD2;
        }
    }
    for (i=n1;i<n2;i++){
        if (nra1==nrb1 && nra2==nrb2){
            nr++;
            if (nr<=1000)
                v[nr]=i-n1;
        }
        nrb1=((((nrb1-((b[i-n1]-'A')*x1)%MOD1+MOD1)%MOD1)*26)%MOD1+b[i]-'A')%MOD1;
        nrb2=((((nrb2-((b[i-n1]-'A')*x2)%MOD2+MOD2)%MOD2)*26)%MOD2+b[i]-'A')%MOD2;
    }
    if (nra1==nrb1 && nra2==nrb2){
        nr++;
        if (nr<=1000)
            v[nr]=n2-n1-1;
    }
    fprintf (fout,"%d\n",nr);
    if (nr>1000)
        nr=1000;
    for (i=1;i<=nr;i++)
        fprintf (fout,"%d ",v[i]);
    return 0;
}