Sum of all LCP of maximum length by selecting any two Strings at a time | C ++ 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 Function
#include <bits/stdc++.h> NEW_LINE using namespace std ; class TrieNode { public : char val ; map < char , TrieNode * > children ; int visited ; TrieNode ( char x ) { val = x ; visited = 0 ; } } ; class Trie { public : TrieNode * head ; Trie ( ) { head = new TrieNode ( ' \0' ) ; } void addWord ( string s ) { TrieNode * temp = head ; const unsigned int n = s . size ( ) ; for ( int i = 0 ; i < n ; i ++ ) { char ch = s [ i ] ; if ( ! temp -> children [ ch ] ) { temp -> children [ ch ] = new TrieNode ( ch ) ; } temp = temp -> children [ ch ] ; temp -> visited ++ ; } } int dfs ( TrieNode * node , int & ans , int depth ) { int vis = 0 ; for ( auto child : node -> children ) { vis += dfs ( child . second , ans , 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 ( ) { int ans = 0 ; dfs ( head , ans , 0 ) ; return ans ; } } ; int main ( ) { Trie T ; 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 ( ) ; cout << ans << endl ; return 0 ; }