According to me, the problem is regarding fastest search of substrings.. Hashing is one of the solutions. Use Rabin-Karp Search.. Use wiki at: http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_string_search_algorithm#Rabin.E2.80.93Karp_and_multiple_pattern_search
On Dec 14, 4:01 pm, sourabh jakhar <sourabhjak...@gmail.com> wrote: > i have a one idea in my mind is to implement a hash table structure based on > 26 alphabets > and a data structure of words. > struct word > { > int info; > char a[n];}; > > structure contains the info about the word and an array in which document > it is present or not out of n > ex if it is word is mnnit and it is in document 1 ,4,6,9 > the info of the structure would be char[1,4,6,9]=1 > and the rest are zero. > insertion of word would take o(1) time but searching would take o(n) time if > list is implemented as an array list > and if implemented as an binary search tree would take it log(n) but than > insertion would also take log(n) time > > > > > > On Mon, Dec 13, 2010 at 9:55 PM, GOBIND KUMAR <gobind....@gmail.com> wrote: > > One of my friends attended google interview.This was one the question > > asked. > > > "you are given N documents(possibly in millions) with words in them. > > design datastructures such that the following scenarios take optimal time: > > > a. print all the the docs having a given word > > > b. print the docs having both of 2 given words" > > > Help me in solving 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 algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > SOURABH JAKHAR,(CSE)(3 year) > ROOM NO 167 , > TILAK,HOSTEL > 'MNNIT ALLAHABAD- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.