Cod sursa(job #171829)

Utilizator savimSerban Andrei Stan savim Data 5 aprilie 2008 11:27:15
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <stdio.h>
#include <string.h>
#define maxl 2000000

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

    q=strlen(b)-1;
    k=0;
    j=1;
    for (i=p; i>=0; i--)
    {
        k=(k+(b[i]-97)*j)%666013;
        j=(j*baz)%666013;
    }
    x=j/baz;

    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*(b[i-p-1]-97)))*baz)%666013;
        if (k<0) k+=666013;
        k=(k+b[i]-97)%666013;
        if (k<0) k+=666013;        

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