How to find the longest common substring?
Hey,
I asked this question a little while back, and got a working solution with the conventional way... Which is, building a table and looking at a diagonal sequence of numbers. But, I was wondering if it was possible to do it using a constant amount of memory.. as in, without the table. Is that even possible?
The only way I can think of doing it is, take the shorter string of the 2, chop it up into all possible substrings, and then see if any of the substrings exist in the bigger of the 2 strings... but this method would take an enormous amount of time...
Is there a slightly more efficient method? Google searches return methods that use a constant time, but not constant memory...
Appreciate any help on this!
I asked this question a little while back, and got a working solution with the conventional way... Which is, building a table and looking at a diagonal sequence of numbers. But, I was wondering if it was possible to do it using a constant amount of memory.. as in, without the table. Is that even possible?
The only way I can think of doing it is, take the shorter string of the 2, chop it up into all possible substrings, and then see if any of the substrings exist in the bigger of the 2 strings... but this method would take an enormous amount of time...
Is there a slightly more efficient method? Google searches return methods that use a constant time, but not constant memory...
Appreciate any help on this!
Last Comment
ASKER CERTIFIED SOLUTION
THIS SOLUTION IS ONLY AVAILABLE TO MEMBERS.
View this solution by signing up for a free trial.
Members can start a 7-Day free trial and enjoy unlimited access to the platform.
SOLUTION
THIS SOLUTION IS ONLY AVAILABLE TO MEMBERS.
View this solution by signing up for a free trial.
Members can start a 7-Day free trial and enjoy unlimited access to the platform.
C++
C++ is an intermediate-level general-purpose programming language, not to be confused with C or C#. It was developed as a set of extensions to the C programming language to improve type-safety and add support for automatic resource management, object-orientation, generic programming, and exception handling, among other features.
58K
Questions
--
Followers
--
Top Experts
Get a personalized solution from industry experts
TRUSTED BY
When building a suffix tree, multiple occurences of a substring in a text are caught and recorded. If the two input strings are concatentated (with you keeping track of the demarcation), then as you build the suffix tree from your two strings, then whenever a substring matches that is in both input strings, you keep track of the largest occurrence.