Cod sursa(job #1001036)

Utilizator alexx.cosmaCosma Cristian Alexandru alexx.cosma Data 24 septembrie 2013 12:25:34
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

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

int aparPos[2000000];

int BN1, BN2;
int baza1 = 2;
int baza2 = 5;

int mod1 = 666013;
int mod2 = 1000007;

void rabinKarp(string a, string b);

int main()
{
    string A,B;
    fin >> A;
    fin >> B;

    rabinKarp(A,B);
    return 0;
}

int hash1(string a)
{
    int sum=0;
    int len = a.size();
    int tempBase = 1;
    for(int i=len-1; i>=0; i--)
    {
        sum += (a[i] * tempBase) % mod1;
        BN1 = tempBase % mod1;
        tempBase =(tempBase* baza1)%mod1;
    }

    return sum % mod1;
}

int hash2(string a)
{
    int sum=0;
    int len = a.size();
    int tempBase = 1;
    for(int i=len-1; i>=0; i--)
    {
        sum += (a[i] * tempBase) % mod2;
        BN2 = tempBase % mod2;
        tempBase = (tempBase*baza2)%mod2;
    }

    return sum % mod2;
}



void rabinKarp(string a, string b)
{
    int sizeA = a.size();
    int sizeB = b.size();

    int nrOfAparitions=0;

    int hash1A = hash1(a);
    int hash2A = hash2(a);
    int hash1B = hash1(b.substr(0,sizeA));
    int hash2B = hash2(b.substr(0,sizeA));

    for (int i=0; i<=sizeB - sizeA ; i++)
    {
        if(hash1A == hash1B)
        {
            if(hash2A == hash2B)
            {
                aparPos[nrOfAparitions]=i;
                nrOfAparitions++;
            }
        }
        hash1B = (hash1B - BN1 * b[i]) % mod1 + mod1;
        hash1B = (hash1B * baza1 + b[i + sizeA]) % mod1;
        hash2B = (hash2B - (BN2 * b[i])) % mod2 + mod2;
        hash2B = (hash2B * baza2 + b[i + sizeA]) % mod2;
    }

    if(nrOfAparitions < 1000)
        fout << nrOfAparitions << '\n';
    else
        fout << 1000 << '\n';

    for(int i=0; i<nrOfAparitions && i < 1000; i++)
    {
        fout << aparPos[i] << ' ';
    }

    fout << '\n';

}