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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
