Cod sursa(job #629189)

Utilizator VladberilaVladutz Vladberila Data 2 noiembrie 2011 20:35:11
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>
#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];
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++;
             pos[nr]=i-M;    
         }             
     }
     g<<nr<<'\n';
     for(i=1;i<=nr;i++)
        g<<pos[i]<<' ';   
     g.close();  
}
int main()
{
    citire();
    match();
    return 0;
}