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.
This is a dynamic programming problem and can be solved in O(mn) time, where m is the length of one string and n is of other.
Like any other problem solved using Dynamic Programming, we will divide the problem into subproblem. Lets say if two strings are x1x2x3....xm and y1y2y3...yn
S(i,j) is the longest common string for x1x2x3...xi and y1y2y3....yj, then
S(i,j) = max { length of longest common substring ending at xi/yj, if ( x[i] == y[j] ), S(i-1, j-1), S(i, j-1), S(i-1, j) }
Here is working program in Java. I am sure you can convert it to C++.: