Cod sursa(job #291108)

Utilizator otilia_sOtilia Stretcu otilia_s Data 29 martie 2009 13:34:25
Problema Potrivirea sirurilor Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <stdio.h>
#include <string.h>
using namespace std;

#define LMAX 2000018

int n,m,p[LMAX];
char a[LMAX],b[LMAX];

void citire()
{
 FILE *fin=fopen("strmatch.in","r");
 fscanf(fin,"%s",&a);
 fscanf(fin,"%s",&b);
 fclose(fin);
}

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

int main()
{
 citire();
 n=strlen(a)-1;
 m=strlen(b)-1;
 prefix();
 int k=0,nr=0;
 int sol[1008];
 int i;
 for (i=1;i<=m;++i)
  {
   while (k>0 && b[i-1]!=a[k]) k=p[k];
   if (a[k]==b[i-1]) k++;
   if (k==n)
    {
     nr++;
     if (nr<1001) sol[nr]=i-n;
     k=p[k];
    }
  }
 FILE *fout=fopen("strmatch.out","w");
 fprintf(fout,"%d\n",nr);
 if (nr>1000) nr=1000;
 for (i=1;i<=nr;i++)
  fprintf(fout,"%d ",sol[i]);
 fclose(fout);
 return 0;
}