Longest Common Prefix using Binary Search | A C ++ Program to find the longest common prefix ; A Function to find the string having the minimum length and returns that length ; A Function that returns the longest common prefix from the array of strings ; We will do an in - place binary search on the first string of the array in the range 0 to index ; Same as ( low + high ) / 2 , but avoids overflow for large low and high ; If all the strings in the input array contains this prefix then append this substring to our answer ; And then go for the right part ; else Go for the left part ; Driver program to test above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findMinLength ( string arr [ ] , int n ) { int min = INT_MAX ; for ( int i = 0 ; i <= n - 1 ; i ++ ) if ( arr [ i ] . length ( ) < min ) min = arr [ i ] . length ( ) ; return ( min ) ; } bool allContainsPrefix ( string arr [ ] , int n , string str , int start , int end ) { for ( int i = 0 ; i <= n - 1 ; i ++ ) for ( int j = start ; j <= end ; j ++ ) if ( arr [ i ] [ j ] != str [ j ] ) return ( false ) ; return ( true ) ; } string commonPrefix ( string arr [ ] , int n ) { int index = findMinLength ( arr , n ) ; int low = 0 , high = index ; while ( low <= high ) { int mid = low + ( high - low ) / 2 ; if ( allContainsPrefix ( arr , n , arr [ 0 ] , low , mid ) ) { prefix = prefix + arr [ 0 ] . substr ( low , mid - low + 1 ) ; low = mid + 1 ; } high = mid - 1 ; } return ( prefix ) ; } int main ( ) { string arr [ ] = { " geeksforgeeks " , " geeks " , " geek " , " geezer " } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; string ans = commonPrefix ( arr , n ) ; if ( ans . length ( ) ) cout << " The ▁ longest ▁ common ▁ prefix ▁ is ▁ " << ans ; else cout << " There ▁ is ▁ no ▁ common ▁ prefix " ; return ( 0 ) ; }