Sum of all LCP of maximum length by selecting any two Strings at a time | Java program to find Sum of all LCP of maximum length by selecting any two Strings at a time ; Using map to store the pointers of children nodes for dynamic implementation , for making the program space efiicient ; Counts the number of times the node is visited while making the trie ; Initially visited value for all nodes is zero ; Head node of the trie is initialize as ' \0' , after this all Strings add ; Function to insert the Strings in the trie ; Inserting character - by - character ; If the node of ch is not present in map make a new node and add in map ; Recursive function to calculate the answer argument is passed by reference ; To store changed visited values from children of this node i . e . number of nodes visited by its children ; Updating the visited variable , telling number of nodes that have already been visited by its children ; If node . visited > 1 , means more than one String has prefix up till this node common in them ; Number of String pair with current node common in them ; Updating visited variable of current node ; Returning the total number of nodes already visited that needs to be updated to previous node ; Function to run the dfs function for the first time and give the answer variable ; Stores the final answer as sum of all depths ; Driver code
import java . util . * ; class GFG { static class TrieNode { char val ; HashMap < Character , TrieNode > children ; int visited ; TrieNode ( char x ) { val = x ; visited = 0 ; children = new HashMap < > ( ) ; } } static class Trie { TrieNode head ; int ans ; Trie ( ) { head = new TrieNode ( ' \0' ) ; ans = 0 ; } void addWord ( String s ) { TrieNode temp = head ; int n = s . length ( ) ; for ( int i = 0 ; i < n ; i ++ ) { char ch = s . charAt ( i ) ; if ( temp . children . get ( ch ) == null ) { temp . children . put ( ch , new TrieNode ( ch ) ) ; } temp = temp . children . get ( ch ) ; temp . visited ++ ; } } int dfs ( TrieNode node , int depth ) { int vis = 0 ; Iterator hmIterator = node . children . entrySet ( ) . iterator ( ) ; while ( hmIterator . hasNext ( ) ) { Map . Entry child = ( Map . Entry ) hmIterator . next ( ) ; vis += dfs ( ( TrieNode ) child . getValue ( ) , depth + 1 ) ; } node . visited -= vis ; int String_pair = 0 ; if ( node . visited > 1 ) { String_pair = ( node . visited / 2 ) ; ans += ( depth * String_pair ) ; node . visited -= ( 2 * String_pair ) ; } return ( 2 * String_pair + vis ) ; } int dfshelper ( ) { ans = 0 ; dfs ( head , 0 ) ; return ans ; } } public static void main ( String args [ ] ) { Trie T = new Trie ( ) ; String str [ ] = { " babab " , " ababb " , " abbab " , " aaaaa " , " babaa " , " babbb " } ; int n = 6 ; for ( int i = 0 ; i < n ; i ++ ) { T . addWord ( str [ i ] ) ; } int ans = T . dfshelper ( ) ; System . out . println ( ans ) ; } }