Do not use data structures like lists, etc , or recursion in this assignment. Pr

Question

Do not use data structures like lists, etc , or recursion in this assignment. Program is completed is Python. Be sure the program works by using the following tests:

1. longestCommonSubstring(s1, s2) [30 pts Write the function, longestCommonSubstring(s1, s2), that takes two possibly-empty strings and returns the longest string that occurs in both strings (and returns the empty string if either string is empty). For example: LongestCommonSubstring("abcdef", "abqrcdest") returns "cde" Longest CommonSubstring("abcdef", "ghi") returns "" (the empty string) If there are two or more longest common substrings, return the lexicographicaly smaller one (ie, just use" to compare the strings). So, for example: LongestCommonSubstring("abcABC", "zzabZZAB") returns "AB" and not "ab" Hint: Start by solving a simpler problem: how would you find and return the longest-matching substring starting from the beginning of each of the strings? Under this restriction LongestCommonSubstring*("abcdef", "abqrcdest") returns "ab" Now imagine you have a helper function that implements that simpler version of longestCommonSubstring. With that helper function, you can solve longestCommonSubstring by generating all possible combinations of the starting places of s1 and s2, and calling the helper function with each. This can help you identify which sequence of matching characters is the longest.

Explanation / Answer

def longestCommonSubstring(a,b):
   s,e,max1=0,0,0
   result=""
   for i in range(0,len(a)):
       for j in range(0,len(b)):

           if a[i]==b[j]:
               s1,e1=i,j

               while s1<len(a) and e1<len(b) and a[s1]==b[e1]:
                   s1+=1
                   e1+=1
               if len(a[i:s1])>=max1:
                   max1=len(a[i:s1])
                   result=a[i:s1]
   return result
# print("abcdef abqrcdest")
print(longestCommonSubstring("abcdef","abqrcdest")=="cde")
# print("abcde ghi")
print(longestCommonSubstring("abcde","ghi")=="")
# print("" ",abqrcdest")
print(longestCommonSubstring("","abqrcdest")=="")
# print("abcde")
print(longestCommonSubstring("abcde","")=="")
# print("abcABC ZZABzzab")
print(longestCommonSubstring("abcABC","ZZABzzab")=="AB")
                  

#please rate and comment

#feel free to ask any queries

#updated

def longestCommonSubstring(sequence1,sequence2):
   max_length=0
   result=""
   for i in range(0,len(sequence1)):
       for j in range(0,len(sequence2)):

           if sequence1[i]==sequence2[j]:#if char matches
               seq1_iterator,seq2_iterator=i,j#initialise iterators
               #keep iterating till we find and mismatch or sequence is over
               while seq1_iterator<len(sequence1) and seq2_iterator<len(sequence2) and sequence1[seq1_iterator]==sequence2[seq2_iterator]:
                   seq1_iterator+=1
                   seq2_iterator+=1
               if len(sequence1[i:seq1_iterator])>=max_length:#if we get a substring that is bigger than previous then update max_length and result
                   max_length=len(sequence1[i:seq1_iterator])
                   result=sequence1[i:seq1_iterator]
   return result
# print("abcdef abqrcdest")
print(longestCommonSubstring("abcdef","abqrcdest")=="cde")
# print("abcde ghi")
print(longestCommonSubstring("abcde","ghi")=="")
# print("" ",abqrcdest")
print(longestCommonSubstring("","abqrcdest")=="")
# print("abcde")
print(longestCommonSubstring("abcde","")=="")
# print("abcABC ZZABzzab")
print(longestCommonSubstring("abcABC","ZZABzzab")=="AB")
                  

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.