Cod sursa(job #333114)

Utilizator warchildmdMihail Burduja warchildmd Data 21 iulie 2009 15:11:31
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 2.14 kb
#include<cstdio>
#include<string.h>
#define NMAX 2000001
#define MOD_1 666013
#define MOD_2 2000013

char sir[NMAX], pat[NMAX];
int N, M, PTHASH_1, PTHASH_2, FIRSTHASH_1, FIRSTHASH_2, pow255_1=1, pow255_2=1, matches, vec[1001];

inline int min(int a, int b)
{
    if(a<b) return a;
    return b;
}

void make_pat_hash() //face hashul patternului
{
    for(int i=1; i<=M; i++)
    {
        PTHASH_1=PTHASH_1*255+pat[i];
        PTHASH_1%=MOD_1;
        PTHASH_2=PTHASH_2*255+pat[i];
        PTHASH_2%=MOD_2;

        FIRSTHASH_1=FIRSTHASH_1*255+sir[i];
        FIRSTHASH_1%=MOD_1;
        FIRSTHASH_2=FIRSTHASH_2*255+sir[i];
        FIRSTHASH_2%=MOD_2;
    }
    if((FIRSTHASH_1==PTHASH_1)&&(FIRSTHASH_2==PTHASH_2))
    {
        matches++;
        if(matches<=1000)
        vec[matches]=1;
    }
}

void make_hash(int x, int y, int &lasthash_1, int &lasthash_2)
{
    lasthash_1-=(sir[x-1]*pow255_1)%MOD_1;
    while(lasthash_1<0)
    {
        lasthash_1+=MOD_1;
    }
    lasthash_1=lasthash_1*255+sir[y];
    lasthash_1%=MOD_1;

    lasthash_2-=(sir[x-1]*pow255_2)%MOD_2;
    while(lasthash_2<0)
    {
        lasthash_2+=MOD_2;
    }
    lasthash_2=lasthash_2*255+sir[y];
    lasthash_2%=MOD_2;

    if((lasthash_1==PTHASH_1)&&(lasthash_2==PTHASH_2))
    {
        matches++;
        if(matches<=1000)
        vec[matches]=x;
    }
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    //scanf("%s",&pat);
    gets(pat);
    M=strlen(pat);
    //scanf("%s",&sir);
    gets(sir);
    N=strlen(sir);
    for(int i = M; i ; --i) pat[i] = pat[i-1];
    for(int i = N; i ; --i) sir[i] = sir[i-1];
    int lasthash_1, lasthash_2;
    for(int i=1;i<M;++i)
    {
        pow255_1*=255;
        pow255_1%=MOD_1;
        pow255_2*=255;
        pow255_2%=MOD_2;
    }
    make_pat_hash();
    lasthash_1=FIRSTHASH_1;
    lasthash_2=FIRSTHASH_2;
    for(int i=2; i<=N-M+1; i++)
    {
        make_hash(i,i+M-1,lasthash_1,lasthash_2);
    }

    printf("%d\n",matches);
    for(int i=1; i<=min(matches, 1000); i++)
    printf("%d ",vec[i]);

    return 0;
}