Cod sursa(job #622503)

Utilizator cristianalex81Cristian Alexandru cristianalex81 Data 18 octombrie 2011 01:37:10
Problema Potrivirea sirurilor Scor 38
Compilator c Status done
Runda Arhiva educationala Marime 1.34 kb
#include <stdio.h>
#include <string.h>
#define dim 2000001
#define p 101
#define m1 100007
#define m2 100021

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

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

void rabin_karp()
{
    int i,mp1=1,mp2=1;
    if (n>=m)
    {
        for (i=0;i<m;i++)
        {
            ha1=(ha1 * p + a[i])%m1;
            ha2=(ha2 * 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(); //check for the first string
        for (i=1;i<n-m;i++)
        {
            ha1=((ha1-(a[i-1]*mp1)%m1 + m1)*p + a[i+m-1])%m1;
            ha2=((ha2-(a[i-1]*mp2)%m2 + m2)*p + a[i+m-1])%m2;
            c[i]=match();
        }
    }
}

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;
}