Cod sursa(job #568350)

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

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

string A, B;

int n, m;
int nr;

void KMP();
void Prefix();
void Write();

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

void KMP()
{
     // prefix;
     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;
     }
     
     //for( int i = 0; i <= A.size(); ++i )
     //     fout << T[i] << ' ';
     
     //KMP;
     
     vector<int> pozitii;
     int sp = 0;
     int kp = 0;
     while( sp < B.size() )
     {
            while( kp != -1 && ( kp == A.size() || A[kp] != B[sp] ) )
                   kp = T[kp];
            
            kp++;
            sp++;
            if( kp == A.size() )
                pozitii.push_back( sp - kp );
     }
     fout << pozitii.size() << '\n';
     int n = pozitii.size();
     if ( n > 1000 )
        n = 1000;
     for( int i = 0; i < n; ++i )
          fout << pozitii[i] << ' ';
}