Cod sursa(job #251691)

Utilizator StigmaSimina Pitur Stigma Data 3 februarie 2009 01:53:46
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
 #include <iostream.h>  
 #include <string.h>
 #include <stdio.h>
   

 char a[2000005],b[2000005];
 long poz[1000005];
 long s,sb[2000005],n,m,nr;

 int verif(int i)
 {long j;
  for (j=n-1;j>=0;j--, i--)
   if (a[j]!=b[i]) return 0;
 return 1;
 }

 int main()
 {long i;

 freopen("strmatch.in","r",stdin);
 freopen("strmatch.out","w",stdout);

 scanf("%s",a);
 scanf("%s",b);

 n=strlen(a);
  m=strlen(b);

 s=(int)a[0];
 sb[0]=b[0];


 for (i=1;i<n;i++)
 {s+=(int)a[i];
  sb[i]=b[i]+sb[i-1];
  }


 for (i=n;i<m;i++)
  sb[i]=sb[i-1]+b[i]-b[i-n];


 for (i=n-1;i<m;i++)
  if (sb[i]==s)
  if (verif(i))
    {nr++;
   if (nr<=1000)
    poz[nr]=i;
    }

 printf("%d\n",nr);

 for (i=1;i<=1000 && i<=nr;i++)
 printf("%d ",poz[i]-n+1);
 return 0;
}