Assumption 1: The alphabet size of the dictionary is a constant 'c' independent of the dictionary size 'n' (a reasonable assumption valid for this case). Assumption 2: Words are allowed to repeat in the array. (Otherwise it's a huge combinations explosion)
Create a 2D array elements such that elements(i, j) = intersection(children(elements(i-1, j)), children(elements(i, j-1))) elements(0, i) and elements(i, 0) point to root nodes in the suffix tree. Make sure you memoize the values (Dynamic programming) Here: * elements(i, j) is a set of pointers into a suffix tree of the words in a dictionary. * intersection(pointer_list1, pointer_list2) keeps all those pointers whose character values are present in both lists and removes duplicate pointers. * children(pointer_list) yields the pointer list of all child nodes of pointers in the pointer_list. By child node, we mean the node corresponding to the next character in a valid word. Algo to get the max rectangle: for(i = 0 to infinity) { if(size(elements(i, 1)) == 0) break; // can't extend column for(j = 0 to infinity) { if(size(elements(i,j)) == 0) break; // can't extend row } } Output (i, j) as the result. Note: This will be a fairly complex algo to implement. -- DK http://twitter.com/divyekapoor http://www.divye.in -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/wA8KF0D17EwJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.