Read each file word by word and insert into a Suffix Tree... Terminal node of each word contains the FileNo/FileName...
Quite simple On Dec 14, 5:42 pm, Tuaa <vention.goth...@gmail.com> wrote: > 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_algorit... > > 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.
