$--$Use C$++$ programming language.

$--$In this assignment, you must have separate interface and implementation files $($i$.$e$.,$ separate $.$h and $.$cpp files$)$ for your class. Your class name MUST BE HashTable and your file names MUST BE HashTable.h and HashTable.cpp$.$ You have to implement Subtask$1.$cpp$,$ Subtask$2.$cpp and Subtask$3.$cpp to solve and test subtasks.Note that you may write additional class$($es$)$ in your solution. Your $.$cpp$,.$h $,.$pdf files, and Makefile $,$ which produces executables for each subtask.

$--$You ARE NOT ALLOWED to use any data structure or algorithm related function from the C$++$ standard template library $($STL$)$ such as vector or any other external libraries.

Question $3-72$ points

Subtask $1$

You are given $n$ unique strings. You want to know the number of pairs $(i,j)$ such that the $i^{th}$ string is either prefix or

suffix of the $j^{th}$ string and $ij.$ To make it clear, an example is given below.

Sample Output$($ pairs.txt$)$

$10$

Explanation:

$1"$ab$"$ is prefix of "abc" $2->"$ab$"$ is prefix of "abcde"

$3->"$ab$"$ is suffix of "cab" $4->"$bc$"$ is suffix of "abc"

$5->"$bc$"$ is prefix of "bcda" $6"$bc$"$ is prefix of "bca"

$7->"$c$"$ is suffix of $"abc"8"c"$ is suffix of $"bc"$

$9"$c$"$ is prefix of "cab" $10->$ ef is suffix of "def"

Important:

If one is both prefix and suffix of another, you need to count it twice.

For example, $"$a$"$ is both prefix and suffix of "aba". So you count it twice.

This homework MUST be done using hashing.

If you try to solve this question using data structures other than hash tables you will get $0$ from this part and FZ

from this course. You MUST implement your hash table using separate chaining.

To get a full credit your code must work correct and work in O$($ total$\_$number$\_$of$\_$characters $).$

The name of the input file will be provided as a command line argument to your program. Thus, your program

should run using two command line arguments. Thus, the application interface is simple and given as follows:

username@dijkstra: $>./$subtask$1nm$ Explanation:

First pattern, $"$bc$",$ occurs at $2,4,11$ and $14$ indices$($ one based indexing$).$

Second pattern, $"$ab$",$ occurs at $1$ and $10.$

Third pattern, $"$cd$",$ occurs at $6,12$ and $16.$

Forth pattern, $"$bcc$",$ occurs at $4$ and $14.$

This subtask MUST be done using hashing.

You don't have to use separate chaining like previous subtask.

To get a full credit your code must work correct and work in $O(n+m)*logm+$ total$\_$number$\_$of$\_$characters $).$

If you try to solve this question using data structures other than hash tables you will get $0$ from this part and FZ

from this course.

$-$The name of the input file will be provided as a command line argument to your program. Thus, your program

should run using two command line arguments. Thus, the application interface is simple and given as follows:

username@dijkstra: $>./$subtask$2n$ The size of the minimal subset is $1.$ Minimal subset can be either "abcde" or "edcba" and its size is $1.$ You need to

have one reverse operation on "abcde" to make it equal to "edcba" or vice versa.

line$).$

Explanation:

The size of the minimal subset is $2.$ Minimal subset can be "baaa", $"$bcd$"$