Pair of strings having longest common prefix of maximum length in given array | C ++ program to implement the above approach ; Structure of Trie ; Function to insert a string into Trie ; Stores length of the string ; Traverse the string str ; If str [ i ] is not present in current path of Trie ; Create a new node of Trie ; Update root ; Function to find the maximum length of longest common prefix in Trie with str ; Stores length of str ; Stores length of longest common prefix in Trie with str ; Traverse the string str ; If str [ i ] is present in the current path of Trie ; Update len ; Update root ; Function to print the pair having maximum length of the longest common prefix ; Stores index of the string having maximum length of longest common prefix ; Stores maximum length of longest common prefix . ; Create root node of Trie ; Insert arr [ 0 ] into Trie ; Traverse the array . ; Stores maximum length of longest common prefix in Trie with arr [ i ] ; If temp is greater than len ; Update len ; Update idx ; Traverse array arr [ ] ; Stores length of arr [ i ] ; Check if maximum length of longest common prefix > M ; Traverse string arr [ i ] and arr [ j ] ; If current character of both string does not match . ; Print pairs having maximum length of the longest common prefix ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct TrieNode { TrieNode * child [ 256 ] ; TrieNode ( ) { child [ 0 ] = child [ 1 ] = NULL ; } } ; void insertTrie ( TrieNode * root , string str ) { int M = str . length ( ) ; for ( int i = 0 ; i < M ; i ++ ) { if ( ! root -> child [ str [ i ] ] ) { root -> child [ str [ i ] ] = new TrieNode ( ) ; } root = root -> child [ str [ i ] ] ; } } int findStrLen ( TrieNode * root , string str ) { int M = str . length ( ) ; int len = 0 ; for ( int i = 0 ; i < M ; i ++ ) { if ( root -> child [ str [ i ] ] ) { len ++ ; root = root -> child [ str [ i ] ] ; } else { return len ; } } return len ; } void findMaxLenPair ( vector < string > & arr , int N ) { int idx = -1 ; int len = 0 ; TrieNode * root = new TrieNode ( ) ; insertTrie ( root , arr [ 0 ] ) ; for ( int i = 1 ; i < N ; i ++ ) { int temp = findStrLen ( root , arr [ i ] ) ; if ( temp > len ) { len = temp ; idx = i ; } insertTrie ( root , arr [ i ] ) ; } for ( int i = 0 ; i < N ; i ++ ) { int M = arr [ i ] . length ( ) ; if ( i != idx && M >= len ) { bool found = true ; for ( int j = 0 ; j < len ; j ++ ) { if ( arr [ i ] [ j ] != arr [ idx ] [ j ] ) { found = false ; break ; } } if ( found ) { cout << " ( " << arr [ i ] << " , ▁ " << arr [ idx ] << " ) " ; return ; } } } } int main ( ) { vector < string > arr = { " geeksforgeeks " , " geeks " , " geeksforcse " } ; int N = arr . size ( ) ; findMaxLenPair ( arr , N ) ; }