Cod sursa(job #1519213)

Utilizator Andrei501Clicinschi Andrei Andrei501 Data 6 noiembrie 2015 23:51:10
Problema Potrivirea sirurilor Scor 78
Compilator c Status done
Runda Arhiva educationala Marime 1.99 kb
#include <stdio.h>
#include <stdlib.h>

#define prim1 100007
#define prim2 100021
#define baza 75

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

    char B[2000001],c;
    int poz[1001];

    int i=0,NA=0,NB=0;
    int na1=0,na2=0,nb1=0,nb2=0,N=0;
    int p1=1,p2=1;

    c=fgetc (fin);
    while (c!='\n')
    {
        NA++;
        na1=(na1*baza+c)%prim1;
        na2=(na2*baza+c)%prim2;
        c=fgetc (fin);
    }

    c=fgetc (fin);
    while (c!='\n')
    {
        NB++;
        B[NB]=c;
        c=fgetc (fin);
    }

    if (NA>NB)
    {
        fprintf (fout,"%d",0);
    }
    else
    {
        for (i=1; i<=NA; i++)
        {
            if (i!=1)
            {
                p1=(p1*baza)%prim1;
                p2=(p2*baza)%prim2;
            }
        }

        for (i=1; i<=NA; i++)
        {
            nb1=(nb1*baza+B[i])%prim1;
            nb2=(nb2*baza+B[i])%prim2;
        }

        if (na1==nb1&&na2==nb2)
        {
            N++;
            poz[N]=1;
        }

        for (i=NA; i<NB; i++)
        {
            nb1=(((nb1-B[i-NA+1]*p1)%prim1+prim1)*baza+B[i+1])%prim1;
            nb2=(((nb2-B[i-NA+1]*p2)%prim2+prim2)*baza+B[i+1])%prim2;

            if (na1==nb1&&na2==nb2)
            {
                N++;
                if (N<=1000)
                {
                    poz[N]=i-NA+1;
                }
            }
        }

        fprintf (fout,"%d\n",N);

        if (N!=0)
        {
            if (N<=1000)
            {
                for (i=1; i<=N; i++)
                {
                    fprintf (fout,"%d ",poz[i]);
                }
            }
            else
            {
                for (i=1; i<=1000; i++)
                {
                    fprintf (fout,"%d ",poz[i]);
                }
            }
        }
        fputc ('\n',fout);
    }

    fclose (fin);
    fclose (fout);
    return 0;
}