Cod sursa(job #171906)

Utilizator savimSerban Andrei Stan savim Data 5 aprilie 2008 13:10:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 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];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    
    scanf("%s",a);
    
    baz=62;prim=3463769;
    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;
    }

    scanf("%s",a);
    q=strlen(a)-1;
    k=0;
    j=1;
    for (i=p; i>=0; i--)
    {
        k=(k+elem[a[i]]*j)%prim;
        if (i==0) x=j;
        j=(j*baz)%prim;
    }

    if (k==nr)
    {
       m++;
       sol[m]=0;          
    }
    

    for (i=p+1; i<=q; i++)
    {
        k=(k-(x*elem[a[i-p-1]]))%prim;
        if (k<0) k+=prim;
        k =(k * baz + elem[a[i]]) % prim;
        if (k==nr)
        {
              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;    
}