Cod sursa(job #1442804)

Utilizator adina0822Ciubotaru Adina-Maria adina0822 Data 26 mai 2015 12:45:32
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
using namespace std;



/*
#include <fstream>
#include <string.h>
ifstream f("strmatch.in");
ofstream g("strmatch.out");
*/


#include <fstream>
#include <string.h>
#define NMax 2000005
FILE *f=fopen ("strmatch.in","r");
FILE *g=fopen ("strmatch.out", "w");
int M,N;
char A[NMax],B[NMax];
int pi[NMax],pos[1024];


void make_prefix()
{
    int q=0,i;

    for(pi[1]=0,i=2;i<=M;i++)
    {
        while(q&&A[q+1]!=A[i])
        q=pi[q];
        if(A[q+1]==A[i])
        ++q;
        pi[i]=q;
    }

}


int main ()
{
  int i,q=0,n=0;
  fscanf(f,"%s",A);
  fscanf(f,"%s",B);
  M=strlen(A);
  N=strlen(B);
  for(i=M;i>=1;i--)A[i]=A[i-1];
  A[0]=' ';
  for(i=N;i>=1;i--)B[i]=B[i-1];
  B[0]=' ';

  make_prefix();

  for(i=1; i<=N; i++)
  {
      while(q&&A[q+1]!=B[i])
      q=pi[q];
      if(A[q+1]==B[i])
      ++q;
      if(q==M)
      {
          q=pi[M];
          n++;
          if(n<=1000)
          pos[n]=i-M;
      }
  }

  fprintf(g,"%d\n",n);
  if(n<=1000) for(i=1; i<=n; i++) fprintf(g,"%d ",pos[i]);
  else for(i=1; i<=1000; i++) fprintf(g,"%d ",pos[i]);

  return 0;

}