Reference no: EM132138194

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.