You'd better wite a program. On 11 окт, 10:42, "Vaibhav Jain" <[EMAIL PROTECTED]> wrote: > Algo: > > 1. initialize final_result array with whole sequence and count number of > keywords in no_of_keys and initialize counter array for keywords with value > zero. > > 2. if sequence_ptr is not null then start scanning the sequence if > keyword_matches() in sequence put into temp_array and update pointer to read > next character and repeat it till keyword unmatches. > > 3. put the value of temp_array into result_array and make temp_array null. > then if > strlen(result_array)< no_of_keys then go to step 2 with updated pointer to > read remaining sequence. > > 4. else check each character of temp_array and if keyword_matches() in > temp_array then increment counter in counter array at corresponding keyword > place in counter array. > > 5. check counter array if all places in array contain non-zero values, then > compare if strlen(result_array)<strlen(final_result) array then > final_result=result_array. > > 6. else (if some places still have zero in counter array) then make zero in > each place of counter array and make result array null and go to step 2 with > updated pointer to read remaining sequence. > > 7. else (if sequence_ptr is null) then print final result. > > Assume keyword_matches() is checking characters of given sequence/pattern > in hash table(hash table stores all the keywords), so it is giving O(1) > complexity. > > This will give O(N) time complexity where N is total no of characters in > sequence(If no_of keywords k<<N). > > Please correct me if i have done any mistake. > > On 9/25/07, Sticker <[EMAIL PROTECTED]> wrote: > > > > > > > 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? > > -- > Vaibhav Jain
--~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
