Cod sursa(job #613348)

Utilizator stay_awake77Cangea Catalina stay_awake77 Data 22 septembrie 2011 09:49:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <cstring>

#define LMAX 2000001
#define B 73
#define MOD1 100007
#define MOD2 100021

using namespace std;

char A[LMAX], S[LMAX];
int LA, LB, HashCt1, HashCt2, HashA1, HashA2, i, Pow1, Pow2, NrSol;
bool OK[LMAX];

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

int main()
{
	in >> A >> S;
	LA = strlen( A );
	LB = strlen( S );
	if( LA > LB )
	{
	    out << 0 << '\n';
	    return 0;
	}

	for( Pow1 = Pow2 = 1, HashA1 = HashA2 = i = 0; i < LA; i++ )
	{
	    HashA1 = ( HashA1 * B + A[i] ) % MOD1;
	    HashA2 = ( HashA2 * B + A[i] ) % MOD2;

	    if( i )
	    {
	        Pow1 = ( Pow1 * B ) % MOD1;
	        Pow2 = ( Pow2 * B ) % MOD2;
	    }
	}

	for( HashCt1 = HashCt2 = i = 0; i < LA; i++ )
	{
	    HashCt1 = ( HashCt1 * B + S[i] ) % MOD1;
	    HashCt2 = ( HashCt2 * B + S[i] ) % MOD2;
	}

    memset( OK, false, sizeof( OK ) );
    NrSol = 0;
	if( HashCt1 == HashA1 && HashCt2 == HashA2 )
        OK[0] = true, ++NrSol;

    for( i = LA; i < LB; i++ )
    {
        HashCt1 = ( ( HashCt1 - (Pow1 * S[i - LA])%MOD1 + MOD1 )*B + S[i] ) % MOD1;
        HashCt2 = ( ( HashCt2 - (Pow2 * S[i - LA])%MOD2 + MOD2 )*B + S[i] ) % MOD2;

        if( HashCt1 == HashA1 && HashCt2 == HashA2 )
            OK[i - LA + 1] = true, ++NrSol;
    }

    out << NrSol << '\n';
    if( NrSol )
    {
        for( NrSol = i = 0; i < LB && NrSol < 1000; i++ )
        if( OK[i] )
            out << i << ' ', ++NrSol;
        out << '\n';
    }

    return 0;
}