Cod sursa(job #629196)

Utilizator VladberilaVladutz Vladberila Data 2 noiembrie 2011 20:43:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define NMax 2000003
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
long urm[NMax], M,N,nr,pos[NMax];
char A[NMax],B[NMax];
long minim(long x, long y)
{
     if(x<y)
        return x;
     return y;
}
void citire()
{
     long i;
     f>>A>>B;
     M=strlen(A);
     N=strlen(B);
     for(i=M;i>0;--i)
        A[i]=A[i-1];
     for(i=N;i>0;--i)
        B[i]=B[i-1];
     f.close();
}
void prefixeaza()
{
     long i,k=0;
     urm[1]=0;
     for(i=2;i<=M;i++)
     {
          while(k && A[k+1]!=A[i])
              k=urm[k];
          if(A[k+1]==A[i])
             ++k;
          urm[i]=k;            
     }
}
void match()
{
     long i,k=0;
     prefixeaza();
     for(i=1;i<=N;i++)
     {
         while(k && A[k+1]!=B[i])
              k=urm[k];
         if(A[k+1]==B[i])
              k++;
         if(k==M)
         {
             nr++;
             if(nr<=1000)
                 pos[nr]=i-M; 
             k=urm[k];   
         }             
     }
     g<<nr<<'\n';
     for(i=1;i<=minim(nr,1000);i++)
        g<<pos[i]<<' ';   
     g.close();  
}
int main()
{
    citire();
    match();
    return 0;
}