CODEWITHSUNDEEP
stringalgorithmsubstring
user2372074
user2372074

Reputation: 851

find most common substring in given string? overlapping is allow

I already searched for posts on this question. But none of them have clear answers.

Find the occurrence of most common substring with length n in given string. For example, "deded", we set the length of substring to be 3. "ded" will be the most common substring and its occurrence is 2. Few post suggest using suffix tree and the time complexity is O(nlgn), space complexity is O(n). First, I'm not familiar with suffix tree. My idea is to use hashmap store the occurrence of each substring with length of 3. The time is O(n) while space is also O(n). Is this better than suffix tree? Should I take hashmap collison into account?

Extra: if above problem is addressed, how can we solve the problem that length of substring doesn't matter. Just find the most common substring in given string.

Upvotes: 2

Views: 813

Answers (1)

user2566092
user2566092

Reputation: 4661

If the length of the most common substring doesn't matter (but say, you want it to be greater than 1) then the best solution is to look for the most common substring of length 2. You can do this with a suffix tree in linear time, if you look up suffix trees then it will be clear how to do this. If you want the length M of the most common substring to be an input parameter, then you can hash all substrings of length M in linear time using hashing with multiply-and-add where you multiply the previous string hash value by a constant and then add the value for the next least significant value in the string, and take the modulus modulo a prime P. If you pick your modulus P for the computed string integers to be a randomly chosen prime P such that you can store O(P) memory, then this will do the trick, in linear time if you assume that your hashing has no collisions. If you assume that your hashing might have a lot of collisions, and the substring is of length M and the total string length is N, then the running time would be O(MN) because you have to check all collisions, which in the worst case could be checking all substrings of length M for example if your string is a string of all one character. Suffix trees are better in the worst case, let me know if you want some details (but not completely, because suffix trees are complicated) and I can explain at a high level how to get a faster solution with suffix trees.

Upvotes: 2

Related Questions