Pair of strings having longest common prefix of maximum length in given array | Java program for the above approach ; class 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
import java . io . * ; import java . util . * ; class TrieNode { TrieNode [ ] child = new TrieNode [ 256 ] ; TrieNode ( ) { } } class GFG { private static void insertTrie ( TrieNode root , String str ) { int M = str . length ( ) ; for ( int i = 0 ; i < M ; i ++ ) { if ( root . child [ str . charAt ( i ) ] == null ) { root . child [ str . charAt ( i ) ] = new TrieNode ( ) ; } root = root . child [ str . charAt ( i ) ] ; } } private static int findStrLen ( TrieNode root , String str ) { int M = str . length ( ) ; int len = 0 ; for ( int i = 0 ; i < M ; i ++ ) { if ( root . child [ str . charAt ( i ) ] != null ) { len ++ ; root = root . child [ str . charAt ( i ) ] ; } else { return len ; } } return len ; } private static void findMaxLenPair ( List < String > arr , int N ) { int idx = - 1 ; int len = 0 ; TrieNode root = new TrieNode ( ) ; insertTrie ( root , arr . get ( 0 ) ) ; for ( int i = 1 ; i < N ; i ++ ) { int temp = findStrLen ( root , arr . get ( i ) ) ; if ( temp > len ) { len = temp ; idx = i ; } insertTrie ( root , arr . get ( i ) ) ; } for ( int i = 0 ; i < N ; i ++ ) { int M = arr . get ( i ) . length ( ) ; if ( i != idx && M >= len ) { boolean found = true ; for ( int j = 0 ; j < len ; j ++ ) { if ( arr . get ( i ) . charAt ( j ) != arr . get ( idx ) . charAt ( j ) ) { found = false ; break ; } } if ( found ) { System . out . println ( " ( " + arr . get ( i ) + " , ▁ " + arr . get ( idx ) + " ) " ) ; return ; } } } } public static void main ( String [ ] args ) { List < String > arr = Arrays . asList ( new String [ ] { " geeksforgeeks " , " geeks " , " geeksforcse " } ) ; int N = arr . size ( ) ; findMaxLenPair ( arr , N ) ; } }