Cod sursa(job #501195)

Utilizator zloteanu.adrianzloteanu adrian nichita zloteanu.adrian Data 14 noiembrie 2010 15:05:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<fstream>
#include<string.h>
using namespace std;
char t[2000001],p[2000001];
int u[2000001],n,m,s[1001];
int main()
{ifstream in("strmatch.in");
ofstream w("strmatch.out");
in>>p>>t;
int i,k=0,q;
m=strlen(p);
n=strlen(t);
int zx,zy=-1;
u[0]=-1;
for(zx=1;zx<m;++zx)
  {while(zy>-1&&p[zy+1]!=p[zx])
	  zy=u[zy];
  if(p[zy+1]==p[zx])
   zy++;
  u[zx]=zy;}
q=-1;
for(i=0;i<n;++i)
  {while(q>-1&&p[q+1]!=t[i])
     q=u[q];
  if(p[q+1]==t[i])
   q++;
  if(q==m-1)
   {k++;
   if(k<=1000)
    s[k]=i-m+1;
   q=u[q];}}
w<<k<<"\n";
for(i=1;i<=k&&i<=1000;++i)
  w<<s[i]<<" ";
return 0;
}