Substring Algorithm

Hi, I have been given a practice problem involving dynamic programming and i would appreciate some help

If you are given 2 strings, str1 and str2, find the longest possible common substring.

So, for example, if given the strings 'rebublican' and 'democrat' (sans quotes), the longest common substring would be 'eca'

republican

democrat

As you can see, the letters do not have to be adjacent but they must be in order

Can someone just give me a push in the right direction? Just ell me how to go about to solve this problem with dynamic programming (pseudocode, maybe)

Please do not just give me the answer (although you probably wont already)

[781 byte] By [C_Zhaoa] at [2007-10-3 5:42:59]

«« Repost for background
»» JFileChooser file name extention queistion

# 1

Forget the computer for a moment. Imagine someone asked you to work it out manually. Describe how you'd do it. Write down the steps. You'll want each step to be as simple and explicit as possible.

jverda at 2007-7-14 23:50:59 >

top of Java-index,Other Topics,Algorithms...

# 2

You might also try googling for "longest common substring algorithm."

jverda at 2007-7-14 23:50:59 >

# 3

Try to solve the following (imho easier) problem using dynamic programming. It might give you some ideas:Given a sequence of n integers. Find the longest increasing subsequence.Example:6, 1, 3, 7, 4, 9, 5, 0, 44, 3

horstmeyera at 2007-7-14 23:50:59 >

# 4

1)read the first string into a string object2)read the 2nd string into a 2ndstring objectcompare these 2 using comparatorif they are equal print them.

cseniejcea at 2007-7-14 23:50:59 >

# 5

@cseniejce:You don't seem to understand the problem. Your answer is definitely no solution.

horstmeyera at 2007-7-14 23:50:59 >

Java programming resources: FAQs, tutorials, compiler and browser download sites, documentation, books lists, IDEs, etc.

Substring Algorithm

Other Topics New Topic

Other Topics Hot Topic

Other Topics

All Classified