A substring is a contiguous sequence of characters from a string. For example, "cde" is a substring of the string "abcdefg". We say that substring s1 is duplicated in string s if s1 shows us in s at least two times, without overlapping. For example, if s"abcdefbcdgh" then there is a duplicated substring of length 3: "bcd". There is no duplicated substring of length 4 and higher a) Write an algorithm in pseudo-code (in file h2.doc) in a function find_dup_str(s, n) that determines whether a string s contains a duplicated substring of a given length n and that returns the first occurring substring of length n that is duplicated (if any) or the empty string, otherwise. For the example above (s "abcdefbcdgh") with substring length 3, the substring to be returned is "bcd". With length 2, the algorithm returns "bc", and not "cd". For this value of parameter s, if the length parameter is 4 or more, the algorithm returns ". Write an algorithm, not a Python program. To get full credit make sure the algorithm has ALL the features required, as explained in the class material. b) Create a new file p2.py where you write a Python function find dup str(s, n) that implements the algorithm from part a). Parameter s is the original string and n is the length of the substring to look for. Your implementation must use string slicing. In file p2.py write after the function definition some code that reads a string and a number from the terminal, and then calls find dup_str(s, n) and prints the result. Use this for testing. c) Write in file h2.doc after part b) an algorithm find max dup(s) that takes a string s as parameter and that determines the longest substring that is duplicated in s. For instance find max_dup("abcdefbcdgh"), the function should return "bcd". If the string s has no duplicated substrings, then the algorithm should return the empty string, e.g. find max_dup("0123456") should return """. This algorithm MUST use the function written for part b), i.e. must make calls to find dup_str(...) and use its result. To get full credit make sure the algorithm has ALL the features required, as explained in the class material. d) Write in file p2.py a function find max_dup(s) that implements the algorithm from part c). In file p2.py, write after the function definition code that reads a string from the terminal in variable s and then calls find max_dup(s) and prints the result. A substring is a contiguous sequence of characters from a string. For example, "cde" is a substring of the string "abcdefg". We say that substring s1 is duplicated in string s if s1 shows us in s at least two times, without overlapping. For example, if s"abcdefbcdgh" then there is a duplicated substring of length 3: "bcd". There is no duplicated substring of length 4 and higher a) Write an algorithm in pseudo-code (in file h2.doc) in a function find_dup_str(s, n) that determines whether a string s contains a duplicated substring of a given length n and that returns the first occurring substring of length n that is duplicated (if any) or the empty string, otherwise. For the example above (s "abcdefbcdgh") with substring length 3, the substring to be returned is "bcd". With length 2, the algorithm returns "bc", and not "cd". For this value of parameter s, if the length parameter is 4 or more, the algorithm returns ". Write an algorithm, not a Python program. To get full credit make sure the algorithm has ALL the features required, as explained in the class material. b) Create a new file p2.py where you write a Python function find dup str(s, n) that implements the algorithm from part a). Parameter s is the original string and n is the length of the substring to look for. Your implementation must use string slicing. In file p2.py write after the function definition some code that reads a string and a number from the terminal, and then calls find dup_str(s, n) and prints the result. Use this for testing. c) Write in file h2.doc after part b) an algorithm find max dup(s) that takes a string s as parameter and that determines the longest substring that is duplicated in s. For instance find max_dup("abcdefbcdgh"), the function should return "bcd". If the string s has no duplicated substrings, then the algorithm should return the empty string, e.g. find max_dup("0123456") should return """. This algorithm MUST use the function written for part b), i.e. must make calls to find dup_str(...) and use its result. To get full credit make sure the algorithm has ALL the features required, as explained in the class material. d) Write in file p2.py a function find max_dup(s) that implements the algorithm from part c). In file p2.py, write after the function definition code that reads a string from the terminal in variable s and then calls find max_dup(s) and prints the result
