Cod sursa(job #171921)

Utilizator savimSerban Andrei Stan savim Data 5 aprilie 2008 13:16:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <stdio.h>
#include <string.h>
#define maxl 2000010

int i,x,p,q,n,ok,m,baz;
int sol[1010];
int elem[125];
unsigned int nr,j,k;
char a[maxl];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    
    scanf("%s",a);
    
    baz=63;
    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);
        j=(j*baz);
    }

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

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

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