Cod sursa(job #1201885)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 26 iunie 2014 13:07:40
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

typedef unsigned long long ull;

const ull BASE = 137;
const int Lmax = 2e6 + 2;

vector <int> match;

char A[Lmax];
char B[Lmax];

int N, M;

ull H[Lmax], Hpow[Lmax];

ull getCodeHash( int i, int dim )
{
    return H[i] - H[i + dim] * Hpow[dim];
}

void pregen()
{
    Hpow[0] = 1;

    for ( int i = 1; i <= M; ++i )
            Hpow[i] = Hpow[i - 1] * BASE;

    H[M + 1] = 0;

    for ( int i = M; i >= 1; i-- )
    {
        H[i] = H[i + 1] * BASE + B[i];
    }
}

int main()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");

    in.sync_with_stdio( false );

    in >> ( A + 1 );
    in >> ( B + 1 );

    N = strlen( A + 1 );
    M = strlen( B + 1 );

    if ( N > M )
    {
        out << "0\n";
        return 0;
    }

    pregen();

    ull hash_p = 0;

    for ( int i = N; i >= 1; i-- )
    {
        hash_p = hash_p * BASE + A[i];
    }

    for ( int i = 1; i <= M - N; ++i )
    {
        if ( getCodeHash( i, N ) == hash_p )
            match.push_back( i - 1 );
    }

    out << match.size() << "\n";

    for ( int i = 0; i < match.size(); ++i )
    {
        out << match[i] << " ";
    }

    return 0;
}