'How to find the longest common substring

What is the best available algorithm to search the longest common substring? Strings contains 16000+ characters and alphabet is ACDT.

  1. Boyer–Moore–Horspool - time taken is very high
  2. Rabin-Karp - worst than 1st one
  3. Suffix tree - 2d array memory overflow

Any other methods or modifications? Actually I want to calculate the average common substring of two genomes.

algorithm


Solution 1:[1]

Gnomes or genomes?!

See here. Dynamic programming may be the route to take?

Also note that the first two algorithms you've listed are for string searching.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Luke

Related Questions