Cod sursa(job #291112)

Utilizator otilia_sOtilia Stretcu otilia_s Data 29 martie 2009 13:37:58
Problema Potrivirea sirurilor Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream.h>
#include <string.h>
#define LMAX 2008
int n,m,p[LMAX];
char a[LMAX],b[LMAX];

void citire()
{
 ifstream fin("strmatch.in");
 fin.getline(a,LMAX);
 fin.getline(b,LMAX);
 fin.close();
}

void prefix()
{
 int k=-1,x;
 p[0]=0;
 for (x=1;x<n;x++)
  {
    while (k>0&&a[k+1]!=a[x]) k=p[k];
    if (a[k+1]==a[x]) k++;
    p[x]=k;
  }
}

int main()
{
 citire();
 n=strlen(a)-1;
 m=strlen(b)-1;
 prefix();
 int k=-1,nr=0;
 int sol[1003];
 int i;
 for (i=0;i<m;i++)
  {
   while (k>0 && b[i]!=a[k+1]) k=p[k];
   if (a[k+1]==b[i]) k++;
   if (k==n-1)
    {
     nr++;
     if (nr<1001) sol[nr]=i-n+1;
     k=p[k];
    }
  }
 ofstream fout("strmatch.out");
 fout<<nr<<"\n";
 if (nr>1000) nr=1000;
 for (i=1;i<=nr;i++)
  fout<<sol[i]<<" ";
 fout<<"\n";
 fout.close();
 return 0;
}