Cod sursa(job #1144431)

Utilizator felixiPuscasu Felix felixi Data 17 martie 2014 08:33:59
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

const int NMAX  = 2000000;
const int MOD   = 666013;
const int base  = 27;

vector <int> H[ MOD ], R;
string S, A;
int lg, ind_sol, nr_sol;

int putere( int a, int p) {
    int R= 1;
    while( p != 0 ) {
        if( p%2 == 1 ) {
            R= (R*a) % MOD;
        }
        p>>= 1;
        a= (a*a) % MOD;
    }
    return R;
}

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

        int key= 0, k= 0;
        for( int i= 0;  i<lg;  ++i ) {
            int nr1= (int)A[i]-'A'+1;
            int nr2= (int)S[i]-'A'+1;
            key= ( key + nr1*putere(base , lg-i-1)%MOD ) % MOD;
            k= ( k + nr2*putere(base , lg-i-1)%MOD ) % MOD;
        }

        if( k == key ) {
            R.push_back( ind_sol );
        }

        ind_sol++;
        int SCADE= putere(base , A.size()-1);

        for( int i= lg;  i<(int)S.size();  ++i, ++ind_sol ) {
            int nr1= (int)S[i-lg]-'A'+1;
            int nr2= (int)S[i]-'A'+1;
            k= ((k-( nr1*SCADE % MOD ) ) * base%MOD + nr2) % MOD;
            if( k == key ) {
                R.push_back( ind_sol );
            }
        }

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

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

    return 0;
}