Okay so I\'m given a very long string, D (something like \"aasdfabananasbadeasdf

Question

Okay so I'm given a very long string, D (something like "aasdfabananasbadeasdfasdfsdaf"). The user is going to input a string, Q and the program should return the location of Q in D. (I.E. the user inputs "ban" then the program should return 7) However, this would be very simple, but I have to use Hash Tables to detect possible matches fast and verify. We need to verify the match, because if we assume that the length is 6 for the queries, then we need to create hash values for all subsequence in length 6 and insert then into the hash table. I can use any HashTable implementation (i.e. linear probing, quadratic probing, double hashing).


I'm having trouble with creating a class that creates a data structure for a long databased string into a hash table (assuming the length of the subsequence is 6). It must also read the input String from the user and run the query. I also must have a loop to allow the insertion of many queries for the same long string.

Explanation / Answer

This is pseudo-code.

For i < longString.length()-6
{
subLong = longString.substring(i, (i+6); //since you can assume the input strings will all be 6 char
hashCode = (hash * subLong.toChar()) % sizeOfHashTable; //change the string to some number val and hash
if(hashTable[hashCode].isEmpty()) //if the location isn't already taken
hashTable[hashCode] = subLong;
else //something at that hash location already
{insert backup hash function here} //linear probing is easiest, hashCode++ till you find an empty slot
}

The size of the hash table should be at least twice the size of the long string you are given.

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

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