Cod sursa(job #538583)

Utilizator andrei.finaruFinaru Andrei Emanuel andrei.finaru Data 21 februarie 2011 18:29:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<fstream.h>
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[20000002],b[2000002];
int nr,p,na,nb,l[2000002],poz[1002];
int main()
{ int i,j=0;
  f.getline(a+1,2000001);
  f.getline(b+1,2000001);
  a[0]=b[0]='0';
  na=strlen(a)-1; nb=strlen(b)-1;
  for(i=2;i<=na;i++)
	  {while(j>0&&a[i]!=a[j+1]) j=l[j];
	   if(a[i]==a[j+1]) j++;
	   l[i]=j;
	  }
  j=0;
  for(i=1;i<=nb;i++)
	  {while(j>0&&b[i]!=a[j+1]) j=l[j];
	   if(b[i]==a[j+1]) j++;
	   if(j==na)
		   {j=l[na];
		    nr++;
			if(nr<1001) poz[nr]=i-na;
		   }
	  }
  g<<nr<<'\n';
  if(nr>1000) nr=1000;
  for(i=1;i<=nr;i++) g<<poz[i]<<' ';
  g<<'\n';
  f.close(); g.close();
  return 0;
}