How to find Longest Common Substring using C++

c++ algorithm lcs
David Gomes picture David Gomes · Apr 20, 2012 · Viewed 39k times · Source

I searched online for a C++ Longest Common Substring implementation but failed to find a decent one. I need a LCS algorithm that returns the substring itself, so it's not just LCS.

I was wondering, though, about how I can do this between multiple strings.

My idea was to check the longest one between 2 strings, and then go check all the others, but this is a very slow process which requires managing many long strings on the memory, making my program quite slow.

Any idea of how this can be speeded up for multiple strings? Thank you.

Important Edit One of the variables I'm given determines the number of strings the longest common substring needs to be in, so I can be given 10 strings, and find the LCS of them all (K=10), or LCS of 4 of them, but I'm not told which 4, I have to find the best 4.

Answer

Adrian McCarthy picture Adrian McCarthy · Apr 20, 2012

Here is an excellent article on finding all common substrings efficiently, with examples in C. This may be overkill if you need just the longest, but it may be easier to understand than the general articles about suffix trees.

Related questions

How to replace all occurrences of a character in string?

What is the effective way to replace all occurrences of a character with another character in std::string?

Read More
What is the most effective way for float and double comparison?

What would be the most efficient way to compare two double or two float values? Simply doing this is not correct: bool CompareDoubles1 (double A, double B) { return A == B; } But something like: bool CompareDoubles2 (double A, double B) { diff = …

Read More
Printing prime numbers from 1 through 100

This c++ code prints out the following prime numbers: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97. But I don't think that's the way my book wants it to be written. It mentions something about square root of a number. So I did try changing my 2nd loop …

Read More