Cod sursa(job #171861)

Utilizator savimSerban Andrei Stan savim Data 5 aprilie 2008 12:21:49
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <stdio.h>
#include <string.h>
#define maxl 2000010

int i,j,x,p,q,n,nr,k,ok,m,baz,prim;
int sol[1010];
int elem[125];
char a[maxl],b[maxl];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    
    scanf("%s",&a);
    scanf("%s",&b);
    
    baz=42;prim=666013;
    j=0;
    for (i='0'; i<='9'; i++)
        elem[i]=++j;
    for (i='a'; i<='z'; i++)
        elem[i]=++j;
    for (i='A'; i<='Z'; i++)
        elem[i]=++j;
        
    
    p=strlen(a)-1;
    j=1;
    nr=0;
    for (i=p; i>=0; i--)
    {
        nr=(nr+elem[a[i]]*j)%prim;
        j=(j*baz)%prim;
    }

    q=strlen(b)-1;
    k=0;
    j=1;
    for (i=p; i>=0; i--)
    {
        k=(k+elem[b[i]]*j);
        while (k>prim) k-=prim;
        if (i==0) x=j;
        j=(j*baz)%prim;
    }

    ok=1;
    for (i=0; i<=p; i++)
    if (a[i]!=b[i])
    {
        ok=0;
        break;
    }
    if (ok)
    {
        m++;
        sol[m]=0;
    }
    

    for (i=p+1; i<=q; i++)
    {
        k=(k-(x*elem[b[i-p-1]]));
        while (k>prim) k-=prim;

        while (k<0) k+=prim;
        k=(k*baz);
        while (k>prim) k-=prim;
        k=(k+elem[b[i]]);
        while (k>prim) k-=prim;

        if (k==nr)
        {
           ok=1;
           for (j=0; j<=p; j++)
               if (a[j]!=b[i-p+j]) {ok=0;break;}
           if (ok) 
           {
              m++;
              if (m<=1000) sol[m]=i-p;        
           }
        }
    }    
    printf("%d\n",m);
    if (m>1000) m=1000;
    for (i=1; i<=m; i++)
        printf("%d ",sol[i]);
    printf("\n");
    
    return 0;    
}