Cod sursa(job #1452478)

Utilizator petru.cehanCehan Petru petru.cehan Data 20 iunie 2015 23:22:05
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 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);
  f[0]=-1;
  for(j=1;j<lgA;++j)
      {
          k=f[j-1];
          while(k!=-1 && A[j-1]!=A[k])
                 k=f[k];
          f[j]=k+1;
      }

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

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