# Program the search string using hashing

• 04-25-2012
new2cs
Program the search string using hashing
The following is the code provided by my friend as a challenge to my knowledge in C. I have put in a decent effort to come with a solution. However, my solution does not execute as desired. I am not able to figure out as to what mistake has happened and would be glad if anyone could correct my code. Thanks.

Code:

``` #include <iostream> #include <cstring> #include <string.h> using namespace std; #define MOD 31 int hash(char* a, int n) {     // Hash function is computed by adding all the characters and     // taking remainder by MOD.     int i;     int sum = 0;     for(i = 0; i < n; i++)         sum += *a++;     return (sum % MOD); } int incremental_hash(int oldhash, char outgoing, char incoming) {     int inchash = oldhash - outgoing + incoming;     return (inchash % MOD); } int match(char* a, int m, char* s, int n) {     // Compare s to substrings of length n.  Return position if match is found, -1 else.     // Strategy: Compute the hash of s.  Compare that hash to the hash of the first n     // positions in a.  If equal, carry out a full character-by-character comparison (use     // memcmp) to determine if s occurs in a. If no match, try the next substring in a.     // Compute the new hash from the old hash by subtracting to the old hash the first character     // of the prior substring and adding the last character of the new substring.     int x, y;     int i = 0;     x = hash(s,n);     y = hash(a,n);     if((x == y) && (memcmp(a, s, n) == 0))       return 0;     else{         for(i = 1; i <= (m-n); ++i){             y = incremental_hash(y, a[i-1], a[i+n-1]);             if((x == y) && (memcmp(i+a, s, n) == 0))                 return i;         }     }     return -1; } int main() {     // Test.     char ASC[NULL];     ASC[0,0] = 'char';      ASC[0,1] = 'ASCII'; ASC[0,2] = ' '; ASC[0,3] = 'char';      ASC[0,4] = 'ASCII'; ASC[0,5] = ' '; ASC[0,6] = 'char';      ASC[0,7] = 'ASCII';     ASC[1,0] = 'A';        ASC[1,1] = '65';    ASC[1,2] = ' '; ASC[1,3] = 'a';        ASC[1,4] = '97';    ASC[1,5] = ' '; ASC[1,6] = '0';        ASC[1,7] = '48';     ASC[2,0] = 'B';        ASC[2,1] = '66';    ASC[2,2] = ' '; ASC[2,3] = 'b';        ASC[2,4] = '98';    ASC[2,5] = ' '; ASC[2,6] = '1';        ASC[2,7] = '49';     ASC[3,0] = 'C';        ASC[3,1] = '67';    ASC[3,2] = ' '; ASC[3,3] = 'c';        ASC[3,4] = '99';    ASC[3,5] = ' '; ASC[3,6] = '2';        ASC[3,7] = '50';     ASC[4,0] = 'D';        ASC[4,1] = '68';    ASC[4,2] = ' '; ASC[4,3] = 'd';        ASC[4,4] = '100';  ASC[4,5] = ' '; ASC[4,6] = '3';        ASC[4,7] = '51';     ASC[5,0] = 'E';        ASC[5,1] = '69';    ASC[5,2] = ' '; ASC[5,3] = 'e';        ASC[5,4] = '101';  ASC[5,5] = ' '; ASC[5,6] = '4';        ASC[5,7] = '52';     ASC[6,0] = 'F';        ASC[5,1] = '70';    ASC[6,2] = ' '; ASC[6,3] = 'f';        ASC[6,4] = '102';  ASC[6,5] = ' '; ASC[6,6] = '5';        ASC[6,7] = '53';     ASC[7,0] = 'G';        ASC[5,1] = '71';    ASC[7,2] = ' '; ASC[7,3] = 'g';        ASC[7,4] = '103';  ASC[7,5] = ' '; ASC[7,6] = '6';        ASC[7,7] = '54';     ASC[8,0] = 'H';        ASC[5,1] = '72';    ASC[8,2] = ' '; ASC[8,3] = 'h';        ASC[8,4] = '104';  ASC[8,5] = ' '; ASC[8,6] = '7';        ASC[8,7] = '55';     ASC[9,0] = 'I';        ASC[5,1] = '73';    ASC[9,2] = ' '; ASC[9,3] = 'i';        ASC[9,4] = '105';  ASC[9,5] = ' '; ASC[9,6] = '8';        ASC[9,7] = '56';     ASC[10,0] = 'J';        ASC[5,1] = '74';    ASC[10,2] = ' ';ASC[10,3] = 'j';        ASC[10,4] = '106';  ASC[10,5] = ' ';ASC[10,6] = '9';        ASC[10,7] = '57';     ASC[11,0] = 'K';        ASC[5,1] = '75';    ASC[11,2] = ' ';ASC[11,3] = 'k';        ASC[11,4] = '107';  ASC[11,5] = ' ';ASC[11,6] = ' ';        ASC[11,7] = ' ';     ASC[12,0] = 'L';        ASC[5,1] = '76';    ASC[12,2] = ' ';ASC[12,3] = 'l';        ASC[12,4] = '108';  ASC[12,5] = ' ';ASC[12,6] = ' ';        ASC[12,7] = ' ';     ASC[13,0] = 'M';        ASC[5,1] = '77';    ASC[13,2] = ' ';ASC[13,3] = 'm';        ASC[13,4] = '109';  ASC[13,5] = ' ';ASC[13,6] = ' ';        ASC[13,7] = ' ';     ASC[14,0] = 'N';        ASC[5,1] = '78';    ASC[14,2] = ' ';ASC[14,3] = 'n';        ASC[14,4] = '110';  ASC[14,5] = ' ';ASC[14,6] = ' ';        ASC[14,7] = ' ';     ASC[15,0] = 'O';        ASC[5,1] = '79';    ASC[15,2] = ' ';ASC[15,3] = 'o';        ASC[15,4] = '111';  ASC[15,5] = ' ';ASC[15,6] = ' ';        ASC[15,7] = ' ';     ASC[16,0] = 'P';        ASC[5,1] = '80';    ASC[16,2] = ' ';ASC[16,3] = 'p';        ASC[16,4] = '112';  ASC[16,5] = ' ';ASC[16,6] = ' ';        ASC[16,7] = ' ';     ASC[17,0] = 'Q';        ASC[5,1] = '81';    ASC[17,2] = ' ';ASC[17,3] = 'q';        ASC[17,4] = '113';  ASC[17,5] = ' ';ASC[17,6] = ' ';        ASC[17,7] = ' ';     ASC[18,0] = 'R';        ASC[5,1] = '82';    ASC[18,2] = ' ';ASC[18,3] = 'r';        ASC[18,4] = '114';  ASC[18,5] = ' ';ASC[18,6] = ' ';        ASC[18,7] = ' ';     ASC[19,0] = 'S';        ASC[5,1] = '83';    ASC[19,2] = ' ';ASC[19,3] = 's';        ASC[19,4] = '115';  ASC[19,5] = ' ';ASC[19,6] = ' ';        ASC[19,7] = ' ';     ASC[20,0] = 'T';        ASC[5,1] = '84';    ASC[20,2] = ' ';ASC[20,3] = 't';        ASC[20,4] = '116';  ASC[20,5] = ' ';ASC[20,6] = ' ';        ASC[20,7] = ' ';     ASC[21,0] = 'U';        ASC[5,1] = '85';    ASC[21,2] = ' ';ASC[21,3] = 'u';        ASC[21,4] = '117';  ASC[21,5] = ' ';ASC[21,6] = ' ';        ASC[21,7] = ' ';     ASC[22,0] = 'V';        ASC[5,1] = '86';    ASC[22,2] = ' ';ASC[22,3] = 'v';        ASC[22,4] = '118';  ASC[22,5] = ' ';ASC[22,6] = ' ';        ASC[22,7] = ' ';     ASC[23,0] = 'W';        ASC[5,1] = '87';    ASC[23,2] = ' ';ASC[23,3] = 'w';        ASC[23,4] = '119';  ASC[23,5] = ' ';ASC[23,6] = ' ';        ASC[23,7] = ' ';     ASC[24,0] = 'X';        ASC[5,1] = '88';    ASC[24,2] = ' ';ASC[24,3] = 'x';        ASC[24,4] = '120';  ASC[24,5] = ' ';ASC[24,6] = ' ';        ASC[24,7] = ' ';     ASC[25,0] = 'Y';        ASC[5,1] = '89';    ASC[25,2] = ' ';ASC[25,3] = 'y';        ASC[25,4] = '121';  ASC[25,5] = ' ';ASC[25,6] = ' ';        ASC[25,7] = ' ';     ASC[26,0] = 'Z';        ASC[5,1] = '90';    ASC[26,2] = ' ';ASC[26,3] = 'z';        ASC[26,4] = '122';  ASC[26,5] = ' ';ASC[26,6] = ' ';        ASC[26,7] = ' ';     cout << "This is the ASCII table:\n";     cout << &ASC << endl;     cout << "\nEnter values to array A:\n";     int i;     int n = 0;     char A[NULL];     while(cin >> i){         A[n] = i;         n++;     }     cin.clear();     cout << "\nEnter values to array B:\n";     int j;     int m = 0;     char B[NULL];     while(cin >> j){       B[m] = j;       m++;     }     int Q;     Q = match(A, n+1, B, m+1);     if(Q == -1)         cout << "\nNOT FOUND!";     else       cout << "\nFOUND AT POSSITION:" << Q;     return 0; }```
• 04-25-2012
jimblumberg
Quote:

However, my solution does not execute as desired.
Please be more specific. Why does your solution not execute as desired? What output do you expect the program to to produce, what output is the program producing? What input did you supply to the program? Also you state this is a challenge of your C knowledge, why are you working on a C++ solution?

Jim
• 04-25-2012
oogabooga
What do you expect this to do?
Code:

`    char ASC[NULL];`
(And there are other lines like that.)

And what is this?
Code:

`ASC[0,0] = 'char';`
There are three things wrong with the above. The first is that you seem to be considering ASC to be a two-dimensional array, but (if it was declared properly) it is only one-dimensional. Second, a two-dim array is not indexed with two numbers separated by a comma but like this ASC[0][0]. Third, you cannot assign a string of characters to a single char.

Also, it is strange that you would type out this whole table when it could easily be created programmatically.
• 04-25-2012
phantomotap
O_o

C++ compilers don't like it when you throw code from another language at it.

Behavior such as that makes compilers cranky.

Soma