Cod sursa(job #1023626)

Utilizator thewildnathNathan Wildenberg thewildnath Data 7 noiembrie 2013 14:48:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include<stdio.h>
#include<string.h>
using namespace std;

#define MOD1 100007
#define MOD2 100013
#define B 87

char a[2000003],b[2000002];
int ha1,ha2,hb1,hb2,n,m;
int poz[2000003];

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    int i,sol=0,b1=1,b2=1;

    scanf("%s\n%s",&a,&b);
    n=strlen(a);
    m=strlen(b);
    if(n>m)
    {
        printf("0\n");
        return 0;
    }
    ///////////////

    for(i=0;i<n;++i)
    {
        ha1=(ha1*B+a[i])%MOD1;
        ha2=(ha2*B+a[i])%MOD2;
    }
    for(i=0;i<n;++i)
    {
        hb1=(hb1*B+b[i])%MOD1;
        hb2=(hb2*B+b[i])%MOD2;
    }
    if(ha1==hb1 &&ha2==hb2)
        poz[++sol]=0;

    for(i=1;i<n;++i)
    {
        b1=(b1*B)%MOD1;
        b2=(b2*B)%MOD2;
    }

    for(;i<m;++i)
    {
        hb1=((hb1 - (b[i-n] * b1) % MOD1 + MOD1) * B + b[i]) % MOD1;
        hb2=((hb2 - (b[i-n] * b2) % MOD2 + MOD2) * B + b[i]) % MOD2;

        if(ha1==hb1 &&ha2==hb2)
            poz[++sol]=i-n+1;
    }




    printf("%d\n",sol);
    if(sol>1000)
        sol=1000;
    for(i=1;i<=sol;++i)
        printf("%d ",poz[i]);
    printf("\n");

    return 0;
}