Cod sursa(job #758440)

Utilizator informatician28Andrei Dinu informatician28 Data 15 iunie 2012 17:48:57
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#define MOD1 100007
#define MOD2 100021
#define P 73

using namespace std;

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

string A, B;
int hashA1, hashA2, hash1, hash2, P1, P2, Nr;
char match[1001];

int main()
{
    int i;

    in >> A >> B;

    int dim_A = A.length();
    int dim_B = B.length();
    P1 = P2 = 1;
    for(i = 0; i < dim_A; i++)
    {
        hashA1 = (hashA1 * P + A[i]) % MOD1;
        hashA2 = (hashA2 * P + A[i]) % MOD2;

        if( i != 0 )
        {
            P1 = (P1 * P) % MOD1;
            P2 = (P2 * P) % MOD2;
        }
    }

    if( dim_A > dim_B )
    {
        out << "0" << '\n';
        return 0;
    }

    for(i = 0; i < dim_A; i++)
    {
        hash1 = (hash1 * P + B[i]) % MOD1;
        hash2 = (hash2 * P + B[i]) % MOD2;
    }

    if( hashA1 == hash1 && hashA2 == hash2 )
    {
        match[0] = 1;
        ++Nr;
    }

    for(i = dim_A; i < dim_B; i++)
    {
        hash1 = ((hash1 - (B[i - dim_A] * P1) % MOD1 + MOD1) * P + B[i]) % MOD1;
        hash2 = ((hash2 - (B[i - dim_A] * P1) % MOD2 + MOD2) * P + B[i]) % MOD2;
        if( hashA1 == hash1 && hashA2 == hash2 )
        {
            match[i - dim_A + 1] = 1;
            ++Nr;
        }
    }
    out << Nr << '\n';
    Nr = 0;
    for(i = 0; i < dim_B && Nr <= 1000; i++)
    {
        if( match[i] )
        {
            ++Nr;
            out << i << " ";
        }
    }
    out << '\n';
    return 0;
}