Cod sursa(job #552349)

Utilizator GrimpowRadu Andrei Grimpow Data 12 martie 2011 09:58:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<iostream.h>
#include<fstream.h>
#include<string.h>
 

 
void prefix(char *N,int *pi)
{    int n,k,i;
    n=strlen(N);
    k=0;
   pi[0]=0;
    for(i=1;i<n;i++)
       {
      while(k>0&& N[k]!=N[i])
        k=pi[k-1];
      if(N[k]==N[i])
     k++;
      pi[i]=k;
       }
}
int main()
{
  char *N = new char[2000001];
   char *M = new char[2000001];
   int i,n,m,q,a[1000],t,s;
   int *pi = new int[2000000];
 ifstream f("strmatch.in");
   f>>N>>M;
  f.close();
  prefix(N,pi);
   t=s=0;
   m=strlen(M);
  n=strlen(N);
  q=0;
   ofstream g("strmatch.out");
   for(i=0;i<m;i++)
      {
      while(q>0 && N[q]!=M[i])
      q=pi[q-1];
      if(N[q]==M[i])
    q++;
     if(q==n&&t<1000) {a[t]=i-n+1; t++; s++;}
      if(q==n&&t>999) s++;
      }
  if(s>999) s--;   
  g<<s<<'\n';
   for(i=0;i<t;i++)
     g<<a[i]<<" ";
   return 0;

 

}