/* * * 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("input.txt"); if (!fin) { cout > testcase; for (int i = 0; i > str; Substring longest = longestSubstring(str); cout

input.txt

5 aaaa abababa abccba CPPisFun theQUICKbrownFOXjumpsOVERtheLAZYdog 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.

Expected 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 theQUICKbrownFOX jumps