Hello all,
This is my first SPOJ problem attempt. I have read a bunch of other entries on the forum about this problem and tried to implement thier advice and test cases, but still am coming up it WA’s. Does anyone have any suggestions?
#include <iostream>
#include <string>
#include <sstream>
#include <fstream>
#include <vector>
using namespace std;
struct item{
item() : isEmpty(1) {}
string key;
int isEmpty;
};
void tablePrint(int maxTableSize, int curTableSize, vector<item>& table);
int Hash(string key);
int h(string key);
int insert(string key, vector<item>& table, int* tableSize);
int remove(string key, vector<item>& table, int* tableSize);
int find(string key, vector<item>& table);
int main(int argc, char* argv[])
{
const int TABLESIZE = 101;
int curTableSize = 0;
vector<item> table(TABLESIZE);
// Read data from the input file:
// first line contains an integer number t (represents the number of test cases <= 100)
// second line contains an integer number n (represents the number of operations, one per line, <=1000
// followed by n lines of operations-> ADD:string or DEL:string
// you code starts here...
string t_str;
string n_str;
getline(cin,t_str);
int t = stoi(t_str);
for(int i = 0; i < t; i++){
getline(cin,n_str);
int n = stoi(n_str);
for(int j = 0; j < n; j++){
string cmd;
getline(cin,cmd);
string key = cmd.substr(4, cmd.length()-1);
if(cmd.substr(0,3) == "ADD"){
int exists = find(key, table);
if(exists == -1){
insert(key, table, &curTableSize);
}
}
else{
remove(key, table, &curTableSize);
}
}
tablePrint(TABLESIZE, curTableSize, table);
for(int k = 0; k < TABLESIZE; k++){
table[k].isEmpty = 1;
}
curTableSize = 0;
}
return 0;
}
// Prints table and number of keys
void tablePrint(int maxTableSize, int curTableSize, vector<item>& table){
cout << curTableSize << endl;
for(int i = 0; i < maxTableSize; i++){
if(!table[i].isEmpty){
cout << i << ":" << table[i].key << endl;
}
}
}
// Return index of a key
int Hash(string key){
return h(key) % 101;
}
// Calculate 19*(ASCII(a1)*1 + ... + ASCII(a2))
int h(string key){
int sum = 0;
// ASCII(a1)*1 + ... + ASCII(an) * n
for(unsigned n = 0; n < key.length(); n++){
sum = sum + key[n]*(n+1);
}
return 19*sum;
}
// Places key at next available index cooresponding with key
//Returns index where key was inserted
int insert(string key, vector<item>& table, int* tableSize){
int index;
// Get index
index = Hash(key);
// If free, put in key
if(table[index].isEmpty){
table[index].key = key;
table[index].isEmpty = 0;
(*tableSize)++;
return index;
}
else{// Perform open addressing collision resolution
for(int j = 1; j <= 19; j++){
index = (Hash(key) + (j*j) + (23*j)) % 101;
if(table[index].isEmpty){
table[index].key = key;
table[index].isEmpty = 0;
(*tableSize)++;
return index;
}
}
return -1; // Assume insert failed
}
}
// Delete key
//Returns index where key was removed
int remove(string key, vector<item>& table, int* tableSize){
int index;
// Get index
index = Hash(key);
// If match, remove key by marking empty
if(table[index].key == key){
table[index].isEmpty = 1;
(*tableSize)--;
return index;
}
else{// Perform open addressing collision resolution
for(int j = 1; j <= 19; j++){
index = (Hash(key) + (j*j) + (23*j)) % 101;
if(table[index].key == key){
table[index].isEmpty = 1;
(*tableSize)--;
return index;
}
}
return -1; // Assume delete failed
}
}
// Finds and returns index of key
int find(string key, vector<item>& table){
int index;
// Get index
index = Hash(key);
// If match, return index
if((table[index].key == key) && !table[index].isEmpty){
return index;
}
else{// Perform open addressing collision resolution
for(int j = 1; j <= 19; j++){
index = (Hash(key) + (j*j) + (23*j)) % 101;
if(table[index].key == key && !table[index].isEmpty){
return index;
}
}
return -1; // Assume find failed
}
}