Cod sursa(job #1201271)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 24 iunie 2014 18:36:59
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

const int BASE = 91;
const int MOD = 1299721;

const int Lmax = 2e6 + 2;

char A[Lmax];
char B[Lmax];
int N, M;

vector <int> match;

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

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

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

    int hashP = 0;
    int rollingHash = 0;
    int baseN = 1;

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

    for ( int i = 1; i <= N; ++i )
    {
        baseN = ( 1LL * baseN * BASE ) % MOD;
        hashP = ( 1LL * hashP * BASE + A[i] ) % MOD;
        rollingHash = ( 1LL * rollingHash * BASE + B[i] ) % MOD;
    }

    if ( hashP == rollingHash )
    {
        match.push_back( 1 );
    }

    for ( int i = N + 1; i <= M; ++i )
    {
        rollingHash = ( ( 1LL * rollingHash * BASE ) % MOD + B[i] - ( 1LL * baseN * B[i - N] ) % MOD + MOD ) % MOD;

        if ( hashP == rollingHash )
        {
            match.push_back( i - N );
        }
    }

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

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

    out << "\n";

    return 0;
}