Longest Common Prefix using Divide and Conquer Algorithm | A C ++ Program to find the longest common prefix ; 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 program to test above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; string commonPrefixUtil ( string str1 , string str2 ) { string result ; int n1 = str1 . length ( ) , n2 = str2 . length ( ) ; for ( int i = 0 , j = 0 ; i <= n1 - 1 && j <= n2 - 1 ; i ++ , j ++ ) { if ( str1 [ i ] != str2 [ j ] ) break ; result . push_back ( str1 [ i ] ) ; } return ( result ) ; } string commonPrefix ( string arr [ ] , int low , int high ) { if ( low == high ) return ( arr [ low ] ) ; if ( high > low ) { int mid = low + ( high - low ) / 2 ; string str1 = commonPrefix ( arr , low , mid ) ; string str2 = commonPrefix ( arr , mid + 1 , high ) ; return ( commonPrefixUtil ( str1 , str2 ) ) ; } } int main ( ) { string arr [ ] = { " geeksforgeeks " , " geeks " , " geek " , " geezer " } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; string ans = commonPrefix ( arr , 0 , n - 1 ) ; if ( ans . length ( ) ) cout << " The ▁ longest ▁ common ▁ prefix ▁ is ▁ " << ans ; else cout << " There ▁ is ▁ no ▁ common ▁ prefix " ; return ( 0 ) ; }