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