Author |
Topic: Frequency of substring (Read 2320 times) |
|
hemanshu
Newbie
Gender: 
Posts: 14
|
 |
Frequency of substring
« on: Mar 1st, 2011, 1:50am » |
 Quote  Modify
|
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
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Frequency of substring
« Reply #1 on: Mar 1st, 2011, 8:43am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Frequency of substring
« Reply #2 on: Mar 1st, 2011, 9:50am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
solid
Newbie
Posts: 5
|
|
Re: Frequency of substring
« Reply #3 on: Sep 4th, 2011, 3:53pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print