1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
#include <iostream>
#include "poszukiwania.h"
#include "message.h"

using namespace std;


typedef long long llong;


template <class T>
T pow_mod(T x, T n, T Mod)
{
    if (n==0)
        return 1;
    else if (n==1)
        return x %Mod;
    else if(n%2==1) //nieparzyste
        return (x *pow_mod(x, n-1, Mod)) %Mod;
    else //parzyste
        return pow_mod((x*x) %Mod, n/2, Mod);
}


class parametry_hashowania
{
public:
    llong Baza, Mod, Dlugosc, Baza_max_pow;
    parametry_hashowania(llong baza, llong mod, llong dl)
    {
        Baza = baza; Mod = mod; Dlugosc = dl;
        Baza_max_pow = pow_mod(Baza, Dlugosc-1, Mod);
    }
    void zmien_dlugosc_sygnalu(llong dl)
    {
        Dlugosc = dl;
        Baza_max_pow = pow_mod(Baza, Dlugosc-1, Mod);
    }
};


template <typename F>
llong policz_hash(F getfun, llong start, const parametry_hashowania& param)
// hash = c_1 *Baza^(dl-1) + c_2 *Baza^(dl-2) +...+ c_{dl-1} *Baza^1 + c_dl *Baza^0
// liczony w arytmetyce modulo Mod
{
    llong hash=0;
    llong Baza_pow = 1; // Baza^0 %Mod - w kolejnych krokach wyzsze potegi
    for (llong ii=start+param.Dlugosc-1; ii>=start; ii--) // sumowanie od konca sygnalu -> najnizsza potegi bazy
    {
        hash += (getfun(ii) *Baza_pow) % param.Mod;
        hash %= param.Mod;
        Baza_pow = (Baza_pow *param.Baza) %param.Mod;
    }
    return hash;
}

llong przesun_hash(llong hash, llong start, const parametry_hashowania& param)
// start - indeks poczatku ciagu w dotychczasowym hashu ; Baza_max_pow = Baza^(dlugosc-1) %Mod
{
    hash -= (SeqAt(start) *param.Baza_max_pow) %param.Mod;
    if (hash<0)
        hash+= param.Mod;
    hash = (hash *param.Baza) %param.Mod;
    hash += SeqAt(start + param.Dlugosc);
    hash %= param.Mod;
    return hash;

}



int main()
{
    llong S = SignalLength();
    llong M = SeqLength();

    llong Baza1 = 1, Baza2 = 3;
    llong Mod = 1000000033; // 10^9+33
    parametry_hashowania param1 = parametry_hashowania(Baza1, Mod, S);
    parametry_hashowania param2 = parametry_hashowania(Baza2, Mod, S);

    // indeksowanie od 1!
    llong hash_sygnal1 = policz_hash(SignalAt, 1, param1);
    llong hash_sygnal2 = policz_hash(SignalAt, 1, param2);
    llong hash_tab1 = policz_hash(SeqAt, 1, param1);
    llong hash_tab2 = policz_hash(SeqAt, 1, param2);

    llong licznik_trafien=0;
    if (hash_tab1 == hash_sygnal1 && hash_tab2 == hash_sygnal2)
        licznik_trafien++;

    for (llong ii=1; ii< M-S+1; ii++)
    {
        hash_tab1 = przesun_hash(hash_tab1, ii, param1);
        hash_tab2 = przesun_hash(hash_tab2, ii, param2);
        if (hash_tab1 == hash_sygnal1 && hash_tab2 == hash_sygnal2)
            licznik_trafien++;
    }

    if (MyNodeId()==0)
        cout<<licznik_trafien<<endl;



    // po zebraniu czesciowych hashy z instancji - pamietaj zmienic Dlugosc w parametrach_hashowania!!!

    return 0;
}