Cod sursa(job #2540155)

Utilizator cyg_contnr1Rares Burghelea cyg_contnr1 Data 6 februarie 2020 19:56:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <stdio.h>
#include <string.h>
#define S 73
#define MAX 2000001
#define MOD1 957091
#define MOD2 666013
char a[MAX],b[MAX];
int v[MAX];
int main()
{
    FILE *fin=fopen("strmatch.in","r");
    FILE *fout=fopen("strmatch.out","w");
    int n,m,i,am1,am2,bm1,bm2,p1,p2,sol=0;

    fscanf(fin,"%s",&a);
    fscanf(fin,"%s",&b);
    n=strlen(a);
    m=strlen(b);
    if(n>m)
        sol=0;
    else
    {
        am1=am2=bm1=bm2=0;
        for(i=0; i<n; i++)
        {
            am1=(am1*S+a[i])%MOD1;
            am2=(am2*S+a[i])%MOD2;
            bm1=(bm1*S+b[i])%MOD1;
            bm2=(bm2*S+b[i])%MOD2;
        }
        if(am1==bm1 && am2==bm2)
            v[sol++]=0;
        p1=p2=1;
        for(i=1; i<n; i++)
        {
            p1=(p1*S)%MOD1;
            p2=(p2*S)%MOD2;
        }
        for(i=n;i<m;i++)
        {
            bm1=((bm1-b[i-n]*p1%MOD1+MOD1)*S+b[i])%MOD1;
            bm2=((bm2-b[i-n]*p2%MOD2+MOD2)*S+b[i])%MOD2;
            if(am1==bm1 && am2==bm2)
                v[sol++]=i-n+1;
        }
    }
    fprintf(fout,"%d\n",sol);
    sol=1000<sol ? 1000:sol;
    for(i=0; i<sol; i++)
        fprintf(fout,"%d ",v[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}