Cod sursa(job #1203728)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 1 iulie 2014 10:44:33
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

typedef unsigned long long ull;

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

vector <int> match;

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

int N, M;

ull H[Lmax], Hpow[Lmax];

ull getHash( int i, int j )
{
    return H[j] - H[i - 1] * Hpow[j - i + 1];
}

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

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

    for ( int i = 1; i <= M; 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 = 1; i <= N; ++i )
    {
        hash_p = hash_p * BASE + A[i];
    }

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

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

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

    return 0;
}