Program the search string using hashing

This is a discussion on Program the search string using hashing within the C++ Programming forums, part of the General Programming Boards category; The following is the code provided by my friend as a challenge to my knowledge in C. I have put ...

  1. #1
    Registered User
    Join Date
    Apr 2012
    Posts
    1

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

  2. #2
    Registered User
    Join Date
    May 2010
    Posts
    2,804
    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

  3. #3
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  4. #4
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,337
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Hashing a string
    By jeanermand in forum C Programming
    Replies: 4
    Last Post: 03-12-2012, 06:58 AM
  2. Hashing Vs Binary Search Trees
    By nickman in forum C Programming
    Replies: 8
    Last Post: 01-10-2011, 11:14 AM
  3. String hashing
    By rags123 in forum C Programming
    Replies: 1
    Last Post: 04-03-2010, 07:47 AM
  4. String hashing
    By jack_carver in forum C Programming
    Replies: 19
    Last Post: 09-11-2009, 07:32 PM
  5. hashing a string
    By cozman in forum C++ Programming
    Replies: 2
    Last Post: 12-31-2001, 11:42 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21