Cod sursa(job #925443)

Utilizator BitOneSAlexandru BitOne Data 24 martie 2013 15:43:11
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <algorithm>

using namespace std;

const int NMAX = 2000011;
const int SOLMAX = 1000;
const int MODULO1 = 100003;
const int MODULO2 = 300007;
const int Alpha = 31;
const int Beta  = 73;

vector<int> matchIdx;

inline int min(const int& x, const int& y) {return x <= y ? x : y;}
void solve(string& pattern, string& s)
{
    int N, M, A, B, i, pHashA, pHashB, sHashA, sHashB;

    N = s.size();
    M = pattern.size();
    A = B = 1;
    pHashA = pHashB = sHashA = sHashB = 0;
    for(i = 0; i < M; ++i)
    {
        pHashA = ( (1LL * pHashA * Alpha) % MODULO1 + pattern[i]) % MODULO1;
        pHashB = ( (1LL * pHashB * Beta) % MODULO2 + pattern[i]) % MODULO2;
        sHashA = ( (1LL * sHashA * Alpha) % MODULO1 + s[i]) % MODULO1;
        sHashB = ( (1LL * sHashB * Beta) % MODULO2 + s[i]) % MODULO2;

        if(i)
        {
            A = (1LL * A * Alpha) % MODULO1;
            B = (1LL * B * Beta) % MODULO2;
        }
    }
    if(pHashA == sHashA && pHashB == sHashB)
    {
        matchIdx.push_back(0);
    }
    for(; i < N; ++i)
    {
        sHashA = ( ((sHashA -  (1LL * A * s[i - M]) % MODULO1 + MODULO1) * Alpha)%MODULO1 + s[i]) % MODULO1;
        sHashB = ( ((sHashB -  (1LL * B * s[i - M]) % MODULO2 + MODULO2) * Beta)%MODULO2 + s[i]) % MODULO2;
        if(pHashA == sHashA && pHashB == sHashB)
        {
            matchIdx.push_back(i - M + 1);
        }
    }
}

int main()
{
    string s, pattern;
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");

    getline(in, pattern);
    getline(in, s);
    solve(pattern, s);
    out << matchIdx.size() << '\n';
    copy(matchIdx.begin(), matchIdx.begin() + min(SOLMAX, matchIdx.size()), ostream_iterator<int>(out, " "));
    out << '\n';

    return EXIT_SUCCESS;
}