Thread: 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;
}

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

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