#include #include #include #include #include using namespace std; /* A location is a set of non-duplicate filenames */ typedef set location_t; /* Input file list maps location names to the sets of files they contain */ typedef map files_t; /* A search path is a list of locations */ typedef vector path_t; /* Input user list maps usernames to search paths */ typedef map users_t; /* * Return true if string "needle" matched "haystack". The "extra" parameter * specified how many additional characters are allowed in "haystack" that * don't match any in "needle". */ bool match(string const &needle, string const &haystack, int extra) { int n = 0; // Iterates over needle characters int h = 0; // Iterates over haystack characters /* Iterate over every character in haystack */ for(h = 0; h < haystack.size() && n < needle.size(); h++) { /* Count each unmatched character in haystack */ if(haystack[h] != needle[n]) { extra--; } /* If these chars match, then advance to the next needle character */ else { n++; } } /* If haystack longer than needle, count trailing haystack chars */ extra -= (haystack.size() - h); /* * Return false if there are too many unmatched characters in haystack or * if haystack was shorter than needle. */ if(n != needle.size() || extra < 0) { return false; } /* Otherwise the match is successful */ return true; } /* * Search for matching filename in each location of a given path. Filenames * and locations are printed out to stdout as they are matched. The "extra" * parameter specifies how many extra unmatched characters are allowed. * Return true if at least one filename matched somewhere in the path. */ bool search(string &filename, path_t &path, files_t &files, int extra) { /* Iterate over every location in the search path */ for(int i = 0; i < path.size(); i++) { location_t &location = files[path[i]]; location_t::iterator j; path_t result; /* Try matching filename against every other file in current location */ for(j = location.begin(); j != location.end(); ++j) { if( match(filename, *j, extra) ) { result.push_back(*j); } } /* If files matched in current location */ if(result.size()) { /* Sort the output alphabetically */ sort(result.begin(), result.end()); /* Print out the result set */ for(int k = 0; k < result.size(); k++) { cout << "FOUND " << result[k] << " IN " << path[i] << endl; } /* Don't search the remaining locations in the path */ return true; } } /* Return false since no matching file names were found */ return false; } /* Main body of program */ void process(void) { int data_num, data_idx; /* Read how many data sets to process */ cin >> data_num; /* Process each data set separately */ for(data_idx = 0; data_idx < data_num; data_idx++) { files_t files; users_t users; /* Read in the list of files and their locations */ int file_count; cin >> file_count; for(int i = 0; i < file_count; i++) { string location, filename; cin >> location >> filename; files[location].insert(filename); } /* Read in the list of users */ int user_count; cin >> user_count; for(int i = 0; i < user_count; i++) { string username; cin >> username; /* Read in the list of locations on this user's search path */ int path_count; cin >> path_count; for(int j = 0; j < path_count; j++) { string location; cin >> location; users[username].push_back(location); } } /* Print dataset header */ cout << "DATA SET #" << data_idx + 1 << endl; /* Read in and process each search request */ int search_count; cin >> search_count; for(int i = 0; i < search_count; i++) { string username, filename; cin >> username >> filename; /* Print search request header */ cout << username << " REQUESTED " << filename << endl; /* Perform search from most to least exact */ search(filename, users[username], files, 0) || search(filename, users[username], files, 1) || search(filename, users[username], files, 2); } } } /* Run program and print out any exceptions that occur */ int main(void) { /* Throw exceptions on failed data extraction in >> operator */ cin.exceptions(ios::failbit); /* Run main body of code */ try { process(); } /* Catch unexpected EOF or bad input data */ catch(ios::failure const &e) { cerr << "Unexpected EOF or data type mismatch on input" << endl; } return 0; }