Cod sursa(job #1334326)

Utilizator gedicaAlpaca Gedit gedica Data 4 februarie 2015 11:18:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX= 2000000, MOD1= 666013, MOD2= 696961, base= 256;

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

vector <int> R;
string S, A;
int lg, ind_sol, nr_sol;


int main()
{
    in >> A >> S;
    if( A.size() <= S.size() )
    {
        lg= A.size();

        int k1= S[0], k2= S[0], h1= A[0], h2= A[0], p1= 1, p2= 1;

        for( int i= 1;  i<lg;  ++i, p1=(p1*base)%MOD1, p2=(p2*base)%MOD2 )
        {
            h1= (h1*base+A[i])%MOD1;
            h2= (h2*base+A[i])%MOD2;
            k1= (k1*base+S[i])%MOD1;
            k2= (k2*base+S[i])%MOD2;
        }

        if( k1==h1 && k2==h2 )
        {
            R.push_back( ind_sol );
            ++nr_sol;
        }

        ++ind_sol;

        for( int i= lg;  i<(int)S.size();  ++i, ++ind_sol )
        {
            k1= ( ( k1 + MOD1 -( S[i-lg]*p1 )%MOD1 )*base + S[i] ) % MOD1;
            k2= ( ( k2 + MOD2 -( S[i-lg]*p2 )%MOD2 )*base + S[i] ) % MOD2;
            if( k1==h1 && k2==h2 )
            {
                ++nr_sol;
                R.push_back( ind_sol );
            }
        }

        out << nr_sol << '\n';

        for( int i=0;  i<(int)R.size() && i<1000;  ++i )
        {
            out << R[i] << ' ';
        }

        out << '\n';
    }

    else out << 0 << '\n';

    return 0;
}