Cod sursa(job #622500)

Utilizator cristianalex81Cristian Alexandru cristianalex81 Data 18 octombrie 2011 01:27:42
Problema Potrivirea sirurilor Scor 14
Compilator c Status done
Runda Arhiva educationala Marime 1.28 kb
#include <stdio.h>
#include <string.h>
#define dim 201
#define p 101
#define m1 100007
#define m2 100021

char a[dim],b[dim];
int n,m,t,c[dim];
int ha1[dim],ha2[dim],hb1,hb2;

inline int match(int i)
{
    if ((ha1[i]==hb1)&&(ha2[i]==hb2))
    {
        t ++;
        return 1;
    }
    return 0;
}

void rabin_karp()
{
    int i,mp1=1,mp2=1;
    for (i=0;i<m;i++)
    {
        ha1[0]=(ha1[0]*p + a[i])%m1;
        ha2[0]=(ha2[0]*p + a[i])%m2;
        hb1 = (hb1*p + b[i])%m1;
        hb2 = (hb2*p + b[i])%m2;
        if (i!=0)
        {
            mp1 = (mp1 * p)%m1; //max power modulo m1 at end of i
            mp2 = (mp2 * p)%m2; //max power modulo m2 at end of i
        }
    }
    c[0]=match(0); //check for the first string
    for (i=1;i<n-m;i++)
    {
        ha1[i]=((ha1[i-1]-(a[i-1]*mp1)%m1 + m1)*p + a[i+m-1])%m1;
        ha2[i]=((ha2[i-1]-(a[i-1]*mp2)%m2 + m2)*p + a[i+m-1])%m2;
        c[i]=match(i);
    }
}

int main()
{
    int i,j;
    freopen ("strmatch.in","r",stdin);
    freopen ("strmatch.out","w",stdout);
    scanf("%s",b);
    scanf("%s",a);
    n = strlen(a);
    m = strlen(b);
    rabin_karp();
    printf("%d\n",t);
    for (i=0,j=0;(j<t)&&(j<1000)&&(i<n-m);i++)
    {
        if (c[i]==1)
        {
            printf("%d ",i);
            j++;
        }
    }
    return 0;
}