Cod sursa(job #812713)

Utilizator maritimCristian Lambru maritim Data 14 noiembrie 2012 11:51:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<stdio.h>

FILE *f = fopen("strmatch.in","r");
FILE *g = fopen("strmatch.out","w");

#define MaxN 2000100
#define MOD1 666013
#define MOD2 1123001
#define MaxSol 1100

int Val1,Val2,Sol;
int SolV[MaxSol];
char A[MaxN],B[MaxN];

void citire(void)
{
    fgets(B,sizeof(B),f);
    fgets(A,sizeof(A),f);
}

void preprocesare(void)
{
    for(int i=0;B[i] != '\n';i++)
        Val1 = (Val1*256+B[i])%MOD1,
        Val2 = (Val2*256+B[i])%MOD2;
}
void rezolvare(void)
{
    int aVal1 = 0,aVal2 = 0,i,put1=1,put2=1,len;

    preprocesare();

    for(i=0;B[i] != '\n';i++)
        aVal1 = (aVal1*256+A[i])%MOD1,
        aVal2 = (aVal2*256+A[i])%MOD2,
        //printf("%d -> %d %d\n",i,aVal1,aVal2),
        i ? (put1 = (put1*256)%MOD1,
        put2 = (put2*256)%MOD2) : 0;

    len = i;

    for(;A[i];i++)
    {
        if(aVal1 == Val1 && aVal2 == Val2)
            if(++Sol <= 1000)
                SolV[Sol] = i-len;
 
        aVal1 = (aVal1+MOD1-(A[i-len]*put1)%MOD1)%MOD1;
        aVal1 = (aVal1*256+A[i])%MOD1;
        aVal2 = (aVal2+MOD2-(A[i-len]*put2)%MOD2)%MOD2;
        aVal2 = (aVal2*256+A[i])%MOD2;

        //printf("%d -> %d %d\n",i,aVal1,aVal2);
    }
}

int main()
{
    citire();
    rezolvare();

    fprintf(g,"%d\n",Sol);
    for(int i=1;i<=1000 && i<=Sol;i++)
        fprintf(g,"%d ",SolV[i]);
}