Cod sursa(job #292598)

Utilizator DjSefuWrong name DjSefu Data 31 martie 2009 12:11:11
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 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[NMAX],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,sizeof(N)-2);
  f.getline(M+1,sizeof(M)-2);
  N[0]=' ';
  M[0]=' ';
  n=strlen(N)-1;
  m=strlen(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;
  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) { k=pi[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;
}