Cod sursa(job #1532862)

Utilizator ZeBuGgErCasapu Andreas ZeBuGgEr Data 21 noiembrie 2015 18:17:34
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include<stdio.h>
#include<string.h>

FILE *fin,*fout;

char s1[2000002],s2[2000002];
int l1,l2;
int res[2000002],pos;
long long int h11,h12,h21,h22;
long long int v1,v2;

int main()
{
    fin=fopen("strmatch.in","r");
    fout=fopen("strmatch.out","w");

    fscanf(fin,"%s",s1+1);
    l1=strlen(s1+1);
    fscanf(fin,"%s",s2+1);
    l2=strlen(s2+1);

    v1=1;
    v2=1;

    for(int i=1;i<=l1;i++)
    {
        h11=(h11*67+s1[i])%100057;
        h12=(h12*67+s1[i])%100043;
        h21=(h21*67+s2[i])%100057;
        h22=(h22*67+s2[i])%100043;
        if(i!=1)
        {
            v1*=67;
            v1%=100057;
            v2*=67;
            v2%=100043;
        }
    }

    //fprintf(fout,"%lld %lld %lld %lld\n",h11,h12,h21,h22);

    if(h11==h21&&h12==h22)
    {
        pos++;
        res[pos]=0;
    }

    for(int i=l1+1;i<=l2;i++)
    {
        h21=((h21-(v1*s2[i-l1])%100057+100057)*67+s2[i])%100057;
        h22=((h22-(v2*s2[i-l1])%100043+100043)*67+s2[i])%100043;
        if(h11==h21&&h12==h22)
        {
            pos++;
            res[pos]=i-l1;
        }
        //fprintf(fout,"%lld %lld %lld %lld\n",h11,h12,h21,h22);
    }

    fprintf(fout,"%d\n",pos);
    if(pos<=1000)
    {
        for(int i=1;i<=pos;i++)
        {
            fprintf(fout,"%d ",res[i]);
        }
    }
    else
    {
        for(int i=1;i<=1000;i++)
        {
            fprintf(fout,"%d ",res[i]);
        }
    }
}