dimanche 11 août 2019

I want to implement rolling hash but I am getting a certain output

Rolling hash---->  Given a string S and pattern P.You need to find all   matches of hash of pattern P in string S.
//Print the index at which pattern's hash is found.If no hash is found print -1.
// String---> bacdaabaa, Pattern---> aab
// Hash value of P... a = 1, b = 2, c = 3, H(P) = 1+1+2 = 4

#include <iostream>
#include <string.h>

using namespace std;

void rolling_hash(string S, string P)
{
    if(P.size() > S.size())
    {
        cout << "-1" << endl;
        return;
    }

    int hash = 0;
    bool flag = false;

    for (int i = 0; i < P.size(); i++)
    {
        hash += (int)(P[i] - 'a') + 1;
    }

    int curr_hash = 0;

    for (int i = 0; i < P.size(); i++)
    {
        curr_hash += (int)(S[i] - 'a') + 1;
    }

    if(curr_hash == hash)
    {
        flag = true;
        cout << S.substr(0, P.size()) << " " << "0\n";
    }

    for (int i = 1; i + P.size() - 1 < S.size(); i++)
    {
        curr_hash = curr_hash + (int)(S[i + P.size() - 1] - 'a') + 1 - (int)(S[i -1] - 'a') + 1;

        if (curr_hash == hash)
        {
            cout << S.substr(i, P.size()) << " " << i << endl;
            flag = true;
        }

        if(!flag) cout << "-1\n";
        return;
    }
}

int main()
{
    string S ="bacdaabaa", P = "aab";
    rolling_hash(S, P);

    return 0;
}

The output is always -1 when I pass the strings but it is giving -1,i.e, it should print the index of matched hash value.please help me out of this...

Rolling hash----> Given a string S and pattern P.You need to find all matches of hash of pattern P in string S. //Print the index at which pattern's hash is found.If no hash is found print -1. // String---> bacdaabaa, Pattern---> aab // Hash value of P... a = 1, b = 2, c = 3, H(P) = 1+1+2 = 4

Aucun commentaire:

Enregistrer un commentaire