troubleshooting Question

How to find the longest common substring?

Avatar of errang
errangFlag for Afghanistan asked on
C++CProgramming Languages-Other
3 Comments2 Solutions748 ViewsLast Modified:
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!
ASKER CERTIFIED SOLUTION
Join our community to see this answer!
Unlock 2 Answers and 3 Comments.
Start Free Trial
Learn from the best

Network and collaborate with thousands of CTOs, CISOs, and IT Pros rooting for you and your success.

Andrew Hancock - VMware vExpert
See if this solution works for you by signing up for a 7 day free trial.
Unlock 2 Answers and 3 Comments.
Try for 7 days

”The time we save is the biggest benefit of E-E to our team. What could take multiple guys 2 hours or more each to find is accessed in around 15 minutes on Experts Exchange.

-Mike Kapnisakis, Warner Bros