Longest Common Prefix using Divide and Conquer Algorithm | A Utility Function to find the common prefix between strings - str1 and str2 ; A Divide and Conquer based function to find the longest common prefix . This is similar to the merge sort technique ; Same as ( low + high ) / 2 , but avoids overflow for large low and high ; Driver Code
def commonPrefixUtil ( str1 , str2 ) : NEW_LINE INDENT result = " " NEW_LINE n1 , n2 = len ( str1 ) , len ( str2 ) NEW_LINE i , j = 0 , 0 NEW_LINE while i <= n1 - 1 and j <= n2 - 1 : NEW_LINE INDENT if str1 [ i ] != str2 [ j ] : NEW_LINE INDENT break NEW_LINE DEDENT result += str1 [ i ] NEW_LINE i , j = i + 1 , j + 1 NEW_LINE DEDENT return result NEW_LINE DEDENT def commonPrefix ( arr , low , high ) : NEW_LINE INDENT if low == high : NEW_LINE INDENT return arr [ low ] NEW_LINE DEDENT if high > low : NEW_LINE INDENT mid = low + ( high - low ) // 2 NEW_LINE str1 = commonPrefix ( arr , low , mid ) NEW_LINE str2 = commonPrefix ( arr , mid + 1 , high ) NEW_LINE return commonPrefixUtil ( str1 , str2 ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ " geeksforgeeks " , " geeks " , " geek " , " geezer " ] NEW_LINE n = len ( arr ) NEW_LINE ans = commonPrefix ( arr , 0 , n - 1 ) NEW_LINE if len ( ans ) : NEW_LINE INDENT print ( " The ▁ longest ▁ common ▁ prefix ▁ is " , ans ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " There ▁ is ▁ no ▁ common ▁ prefix " ) NEW_LINE DEDENT DEDENT