//main.cpp #include <string> #include <iostream> #include<algorithm> using names

Question

//main.cpp

#include <string>

#include <iostream>

#include<algorithm>

using namespace std;

unsigned long bernstein(string str, int M)

{

   unsigned long b_hash = 5381;

   //Your code here

   return b_hash % M;

}

string reverse(string str)

{

   string output = "";

   //Your code here

   return output;

}

int main()

{

   string s = "POTS";

   int M = 13;

   cout<<"Bernstein hash of "<<s<<" with range "<<M<<" is: "<<bernstein(s, M)<<' ';   

   cout<<"Bernstein hash of the reverse of "<<s<<" - " <<reverse(s)<<" - with range "<<M<<", is: "<<bernstein(reverse(s), M)<<' ';

}

The Problem Task 1: Implement the Bernstein hash function Today, we construct a more sophisticated hash function, called the Bernstein hash. For a string str the Bernstein hash b hash, is computed by iterating over its characters. The pseudo-code is as shown below b hash 5381 for all character in str b hash 33 character //use the ASCII value of the character here The magic number 33 is used simply because it works! Why it works better than many other constants, prime or not has never been adequately explained. Your task is to write a function unsigned long int bernstein (string str) that takes in a string as an input and returns its hash. Notice how quickly the hash grows with the length of the input string. Task 2: Effect of character ordering on the Bernstein hash Recall that the additive hash (the one you implemented in the last We'll now test the hash function with various input invariant to the ordering of the letters in a string. Thus, POTS and STOP have the same additive hash. This is usually not desirable. We first like to see if the Bernstein hash function is sensitive to the ordering of characters. To do so, we'll compare the hashes of a string and its reverse. Write a function revers o invert a string, and check if the Bernstein hash for a string changes if the string is inverted. Example output: Bernstein hash of POTS with range 13 is 6 Bernstein hash of the reverse of POTS STOP with range 13, is: 7 Compile and Test A complete Makefile and a main.cpp file containing one simple test has been provided for you. To compile and run, run: make /main

Explanation / Answer

Find the below code for the above problem statement

main.cpp

***********************

#include<stdio.h>
#include <string.h>
#include <iostream>
#include<algorithm>
using namespace std;

unsigned long bernstein(string str, int m)
{
unsigned long b_hash = 5381;
  
//Your code here
  
   for(int m=0; m< str.length(); ++m)
   b_hash=33*b_hash + 'A';
  
return b_hash % m;
}

void reverse(char* str){
   int length = strlen(str);
   char temp;
   for(int i = 0, j = length-1;i < (length-1)/2; i++, j--){
       temp = str[i];
       str[i]=str[j];
       str[j] = temp;
   }
   return;
}

int main()
{
string s = "POTS";
int M = 13;
cout<<"Bernstein hash of "<<s<<" with range "<<M<<" is: "<<bernstein(s, M)<<' ';   
cout<<"Bernstein hash of the reverse of "<<s<<" - " <<reverse(s)<<" - with range "<<M<<", is: "<<bernstein(reverse(s), M)<<' ';
}

************************

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.