We help IT Professionals succeed at work.
Get Started

How to find the longest common substring?

errang
errang asked
on
744 Views
Last Modified: 2012-05-11
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!
Comment
Watch Question
CERTIFIED EXPERT
Most Valuable Expert 2014
Top Expert 2015
Commented:
This problem has been solved!
Unlock 2 Answers and 3 Comments.
See Answers
Why Experts Exchange?

Experts Exchange always has the answer, or at the least points me in the correct direction! It is like having another employee that is extremely experienced.

Jim Murphy
Programmer at Smart IT Solutions

When asked, what has been your best career decision?

Deciding to stick with EE.

Mohamed Asif
Technical Department Head

Being involved with EE helped me to grow personally and professionally.

Carl Webster
CTP, Sr Infrastructure Consultant
Ask ANY Question

Connect with Certified Experts to gain insight and support on specific technology challenges including:

  • Troubleshooting
  • Research
  • Professional Opinions
Did You Know?

We've partnered with two important charities to provide clean water and computer science education to those who need it most. READ MORE