Cod sursa(job #1452324)

Utilizator petru.cehanCehan Petru petru.cehan Data 20 iunie 2015 16:07:37
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <string.h>
#include <fstream>
#define NMAX 2000000
#define minim ((1000>N) ? N : 1000)

using namespace std;

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

char A[NMAX],B[NMAX];
int f[NMAX],sol[NMAX],i,j,k,N;

void Citire()
{
    fin.getline(A,NMAX);
    fin.getline(B,NMAX);
}

void FAILURE(char A[NMAX])
{
  int k,lgA=strlen(A);
  k=0;
  f[1]=0;
  for(j=2;j<=lgA;++j)
      {
          while(k>0 && A[j]!=A[k+1])
                 k=f[k];
          if(A[k+1]==A[j])
              ++k;
          f[j]=k;
      }
}

void KMP(char A[NMAX], char B[NMAX])
{
    i=1;
    j=0;
    int lgA=strlen(A),lgB=strlen(B);
    for(i=1;i<=lgB;++i)
       {
            while(j>0 && A[j+1]!=B[i])
                    j=f[j];
            if(A[j+1]==B[i])
               ++j;
            if(j==lgA)
                {sol[N]=i-lgA,j=f[lgA],++N;}

        }
}
int main()
{
    Citire();
    FAILURE(A);
    KMP(A,B);
    fout<<N<<"\n";
    for(i=0;i<minim;++i)
         fout<<sol[i]<<" ";
    return 0;
}