Cod sursa(job #1144442)

Utilizator felixiPuscasu Felix felixi Data 17 martie 2014 09:23:40
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

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

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= 0, k2= 0, h1= 0, h2= 0, p1= 1, p2= 1;
        for( int i= 0;  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;
        }
        p1/= base;    p2/= base;

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

        for( int i= lg;  i<(int)S.size();  ++i, ++ind_sol ) {
            k1= k1-(int)S[i-lg];    k2= k2-(int)S[i-lg];
            k1/= p1;      k2/= p2;
            k1= (k1+p1*(int)S[i])%MOD1;    k2= (k2+p2*(int)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;
}