Cod sursa(job #1001044)

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

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

int aparPos[2000000];

int BN1 = 1, BN2 = 1;
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();
    BN1 = 1;
    for(int i=0; i< len; ++i)
    {
        sum = (sum * baza1 + a[i]) % mod1;
        if(i){
            BN1 = (BN1 * baza1) % mod1;
        }

    }

    return sum;
}

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

    }

    return sum;
}



void rabinKarp(string a, string b)
{
    int sizeA = a.size();
    int sizeB = b.size();
    int nrOfAparitions=0;
    if(sizeA > sizeB) {
        fout << 0 << '\n';
        return ;
    }
    int hash1A = hash1(a);
    int hash2A = hash2(a);
    string c;
    for(int i = 0; i < sizeA; ++i) {
            c+=b[i];
    }
    int hash1B = hash1(c);
    int hash2B = hash2(c);
    b.push_back('0');
    for (int i=0; i<=sizeB - sizeA ; i++)
    {
        if(hash1A == hash1B)
        {
            if(hash2A == hash2B)
            {
                if(nrOfAparitions < 1000) {
                    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;
    }

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

    fout << '\n';

}