Cod sursa(job #292630)

Utilizator DjSefuWrong name DjSefu Data 31 martie 2009 12:27:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<fstream>
#define NMAX 2000412
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char N[NMAX],M[NMAX];
int i,j,n,m,pi[NMAX],rez[1200],p,k;
void mpre()
{ int k=0;
  pi[1]=0;
  for(int i=2;i<=n;++i) 
  { while(k>0&&(N[k+1]!=N[i])) k=pi[k];
    if(N[k+1]==N[i]) ++k;
    pi[i]=k;
}
}  
int main()
{ f.getline(N+1,NMAX+1);
  f.getline(M+1,NMAX+1);
  N[0]=' ';
  M[0]=' ';
  n=1;
  m=1;
  while((N[n]>='0'&&N[n]<='9')||(N[n]>='a'&&N[n]<='z')||(N[n]>='A'&&N[n]<='Z'))
                                                                                ++n;
  while((M[m]>='0'&&M[m]<='9')||(M[m]>='a'&&M[m]<='z')||(M[m]>='A'&&M[m]<='Z')) ++m;
  --n;
  --m;
  mpre();
  k=0;
  for(i=1;i<=m;++i) 
  { while(k>0&&N[k+1]!=M[i]) k=pi[k];
    if(N[k+1]==M[i]) ++k;
    if(k==n) { 
               if(p<1000) rez[++p]=i-n;
               }
  }
  g<<p<<"\n";
  if(p>1000) p=1000;
  for(i=1;i<=p;++i) g<<rez[i]<<" ";
  g<<"\n";
  f.close();
  g.close();
  return 0;
}