Cod sursa(job #568352)

Utilizator david_raucaRauca Ioan David david_rauca Data 31 martie 2011 09:12:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include<fstream>
#include<vector>
using namespace std;

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

string A;
string B;

void KMP();

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

void KMP()
{
     vector<int> T( A.size() + 1, -1 );
     for( int i = 1; i <= A.size(); ++i )
     {
          int pos = T[i-1];
          while( pos != -1 && A[pos] != A[i-1] )
                 pos = T[pos];
          
          T[i] = pos + 1;
     }
     
     vector<int> pozitii;
     int ap = 0;
     int bp = 0;
     while( bp < B.size() )
     {
            while( ap != -1 && ( ap == A.size() || A[ap] != B[bp] ) )
                   ap = T[ap];
            
            ap++;
            bp++;
            
            if( ap == A.size() )
                pozitii.push_back( bp - ap );
     }
     
     fout << pozitii.size() << '\n';
     int n = pozitii.size();
     if( n > 1000 )
         n = 1000;
     for( int i = 0; i < n; ++i )
          fout << pozitii[i] << ' ';
}