Cod sursa(job #300661)

Utilizator hasegandaniHasegan Daniel hasegandani Data 7 aprilie 2009 16:29:28
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<stdio.h>
#include<string.h>

#define Q 1023
#define Nmax 2000000

char T[Nmax],P[Nmax];
int m,n,b,v[Nmax];

void verif(int k)
{
    for(int i=k;i<k+m;++i)
        if (T[i]!=P[i-k])
            return ;
    v[++v[0]]=k;
}

void rabin_karp()
{
    int i,p=0,t=0,x=1;
    for(i=1;i<m;++i)
        x=(x*(b+1)) % Q;
    for(i=0;i<m;++i)
        {
            p=((b+1)*p + P[i]) % Q;
            t=((b+1)*t + T[i]) % Q;
        }
    for(i=0;i+m<=n;++i)
        {
            if (t==p)
                verif(i);
            t=(t+Q-(x*T[i])%Q)%Q;
            t=((b+1)*t+T[i+m])%Q;
        }
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",T);
    scanf("%s",P);
    
    m=strlen(P),n=strlen(T),b=10;
    rabin_karp();
    
    printf("%d\n",v[0]);
    for(int i=1;i<=v[0];++i)
        printf("%d ",v[i]);
        
    return 0;
}