i believe that your proble is somewhat closely related with Longest common subsequence(which can be solved by DP)between two strings,albeit the problem that you have more than two strings intuitively for me means that as if you have two strings the complexity is O(nm) because you fill in an 2 dimensional array,where |x|=n,|y|=m,then in that case that you have another string(say it z,with |z|=k) then you have a 3 dimensional array ,which means that the complexity might be O(nmk).Well i don't know but i will try to solve it and see it more thoroughly,but something inner to me tells me that you problem might have an exponential algorithm ,and a reduction may be by clique prolem which is NP-complete,i will try my ideas and find a good gadget(i believe that the generalized problem of max common subword of k strings may lie in the NP class) Cheers, Yannis
--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. 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 -~----------~----~----~----~------~----~------~--~---
