Declare: this question is originally from Google. The original form is: given a document, how to find a shortest summary containing all the key words. After translated, it will be: given a sequence, how to find a shortest substring that contains all the items required. Example: a sequence "abaccdefgacel" and a set of key words "a", "c", "d" and "e". The shortest substring contianing all of the key words is "accde". Find one of such shortest substrings. In the original question, there is time complexity boundary O(N), where N is the length of the sequence.
To me, this problem is rather questionable. So far my solution requires a hash table that gives no conflict and can locate a key word in O(1) time. Otherwise the time complexity will definitely be related to the number of key words. Does anyone have idea for a O(N) algorithm to solve this problem? --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
