Cod sursa(job #567895)

Utilizator david_raucaRauca Ioan David david_rauca Data 30 martie 2011 16:28:03
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include<fstream>
using namespace std;

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

char A[2000001];
char B[2000001];

void KMP();
int a[1001];

int main()
{
    fin >> A;
    fin >> B;
    
    KMP();
    
    fin.close();
    fout.close();
    
    return 0;
}

void KMP()
{
     int ok;
     int nr_ap = 0;
     int iaux;
     int n = strlen(B);
     int m = strlen(A);
     for( int i = 0; i < n; ++i )
     {
          ok = 1;
          iaux = 0;
          for( int j = 0; j < m; ++j )
               if( B[i+j] != A[j] )
               {
                   ok = 0;
                   i += iaux;
                   break;
               }  
               else
                   iaux++;   
          
          if( ok == 1 )
          {
              nr_ap++;
              if( nr_ap <= 1000 )
                  a[nr_ap] = i;
          }     
     }
     
     fout << nr_ap << '\n';
     if( nr_ap > 1000 )
         nr_ap = 1000;
     for( int i = 1; i <= nr_ap; ++i )
          fout << a[i] << ' ';
}