wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Frequency of substring
        
(Message started by: hemanshu on Mar 1^st, 2011, 1:50am)

Title: Frequency of substring
Post by hemanshu on Mar 1^st, 2011, 1:50am

I want to rank the substrings occurring multiple times in a string according to their frequency of occurrence in a string. example :
strings is abcdabceabcfabcabcd

ans is abc : 5
abcd:2

Title: Re: Frequency of substring
Post by towr on Mar 1^st, 2011, 8:43am

Sounds like something you could use a trie for.
A trie can give you all the positions where a substring occurs, so just counting that number of positions will give you the frequencies.

Title: Re: Frequency of substring
Post by Grimbal on Mar 1^st, 2011, 9:50am

I would have proposed a suffix tree.

It is not very different from tries (prefix trees). But it adds pointers that make it possible to build the tree from a string in O(n) time and memory,

So if your string could be a rather thick book, this would be worth considering.

Title: Re: Frequency of substring
Post by solid on Sep 4^th, 2011, 3:53pm

Can be solved by 2 ways:
1) Suffix Tree
2) Robin Karp Algorithm: Calculate Hash for pattern and text and then find the same hash in text.