maddy
BAN USERuse suffix tree... create suffix tree of both strings... and at end of each branch out the string name... if any branch has both strings name, then you last complete word before the leaf node is the longest suffix.... then you can append string2 to string 1, where string 2 is starting from 0 + len of longest suffix
- maddy June 12, 2012logic, an last ancestor is the one whose left child is smaller than parent and right child bigger than parent.
this is O(logn)
printAncestor(root, a, b) {
if (root == NULL)
return;
else {
if (root->data > a && root->data > b)
printf(root->data);
printAncestor(root->left, a, b);
} else if (root->data < a && root->data < b) {
printf(root->data);
printAncestor(root->right, a, b);
} else if (root->data > a && root->data < b) {
printf("Last Ancestor", root->data);
printAncestor(root->left, a, b);
}
Think of this problem in terms of graph. lets say the "n" marks where we have to make a cut are "n" vertices and the cost of moving the ace from vertex V1 to V2 the length of log form V1 to V2.... now we have to cover all vertices while minimizing the cost...
thus this can be reduced to spanning tree problem and our goal is to find minimum spanning tree.... there are 2 algorithms for this... Prims and Kruskal.. they each have pros and cons... but any of them will solve the problem....
its same as given two link list that merge at a point... find the merging point...
- maddy June 14, 2012logic:
1) Start pointer1 and count number of nodes to root (len1)
2) Start pointer2 and count number of nodes to root (len2)
3) Max(len1, len2) say len1
4) Move pointer 1 by difference of len1-len2
5) then move both of them together untill you have ptr1!=ptr2