/* * * Find the last occurrence of the longest substring without repeating characters. * You are asked to implement the function longestSubstring() as specified below. * */ #include #include #include #include using namespace std; #define MAX_LENGTH 1000 // the max allowed input string length struct Substring { // the structure used to store the function output int start; // the start position of the longest substring int length; // the length of the longest substring }; //-------------------------- functions to be implemented by you /* * Given a c-string str, find the last occurrence of the longest substring without repeating characters. * * Return a Substring object having the start position and the length of the longest substring. * * Precondition: the input string str is non-empty and contains ASCII characters only. * * Time Complexity Requirement: O(n) * */ Substring longestSubstring(char *str) { } //-------------------------- functions prepared for you /* * Driver program * * Read the test cases from the input file and use them to test * your implementation of longestSubstring(). * */

int main(int argc, char** argv) { char str[MAX_LENGTH]; // buffer ifstream fin("tut02_input.txt"); if (!fin) { cout << "Input file not found."; exit(1); } int testcase = 0; fin >> testcase; for (int i = 0; i < testcase; i++) { fin >> str; Substring longest = longestSubstring(str); cout << "Case " << i + 1 << endl; printf("The substring (%d,%d) is %.*s ", longest.start, longest.length, longest.length, str + longest.start); cout << endl; } fin.close(); return 0; }

5 aaaa abababa abccba CPPisFun theQUICKbrownFOXjumpsOVERtheLAZYdog ========================================================================== ====== Below is the description of the input format and expected output. ========================================================================== ====== Input: The first line of input contains an integer T denoting the number of test cases. Each following line is a test case that contains a string of ASCII characters. Output: Case 1 The substring (3,1) is a Case 2 The substring (5,2) is ba Case 3 The substring (3,3) is cba Case 4 The substring (2,6) is PisFun Case 5 The substring (0,21) is theQUICKbrownFOXjumps