Cod sursa(job #543959)

Utilizator andreea1coolBobu Andreea andreea1cool Data 28 februarie 2011 20:24:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<stdio.h>
#include<string.h>
const int maxp=2000001;
const int p=73;
const int m1=100007;
const int m2=100021;
char a[maxp],b[maxp],m[maxp];
int i,nr1,nr2,h1,h2,d1=1,d2=1,ha1,ha2,sol;
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(a);
    gets(b);
    nr1=strlen(a);
    nr2=strlen(b);
    if(nr1>nr2)
    {
        printf("0");
        return 0;
    }
    for(i=0;i<nr1;i++)
    {
        ha1=(ha1*p+a[i])%m1;
        ha2=(ha2*p+a[i])%m2;
        h1=(h1*p+b[i])%m1;
        h2=(h2*p+b[i])%m2;
    }
    for(i=1;i<nr1;i++)
    {
        d1=(d1*p)%m1;
        d2=(d2*p)%m2;
    }
    if(h1==ha1&&h2==ha2)
        sol++, m[0]=1;
    for(i=nr1;i<nr2;i++)
    {
        h1=((h1-(b[i-nr1]*d1)%m1+m1)*p+b[i])%m1;
        h2=((h2-(b[i-nr1]*d2)%m2+m2)*p+b[i])%m2;
        if(h1==ha1&&h2==ha2)
        sol++, m[i-nr1+1]=1;
    }
    printf("%d\n",sol);
    sol=0;
    for(i=0;i<nr2&&sol<1000;i++)
        if(m[i]==1)
            printf("%d ",i),sol++;
    return 0;
}