Cod sursa(job #251346)

Utilizator StigmaSimina Pitur Stigma Data 2 februarie 2009 13:26:35
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream.h>
#include <fstream.h>
#include <string.h>

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char a[2000000],b[2000000];
long poz[1005];
long s,sb[2000000],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;

 fin>>a;
 fin>>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;
   }

fout<<nr<<'\n';

for (i=1;i<=1000 && i<=nr;i++)
fout<<poz[i]-n+1<<" ";
fout.close();
return 0;
}