Finding partial substrings within a string

Question

I have two strings which must be compared for similarity. The algorithm must be designed to find the maximal similarity. In this instance, the ordering matters, but intervening (or missing) characters do not. Edit distance cannot be used in this case for various reasons.

The situation is basically as follows:

string 1: ABCDEFG
string 2: AFENBCDGRDLFG

the resulting algorithm would find the substrings A, BCD, FG

I currently have a recursive solution, but because this must be run on massive amounts of data, any improvements would be greatly appreciated

Can you post a description of your current, recursive solution? — Ani
– Ani, Commented Sep 20, 2010 at 3:19
@Peter: The reason I removed the substring tag was that substrings are always consecutive. What you want is a subsequence which need not be consecutive. — codaddict
– codaddict, Commented Sep 20, 2010 at 3:40

codaddict · Accepted Answer · 2010-09-20 03:27:00Z

5

Looking at your sole example it looks like you want to find longest common subsequence. Take a look at LCS

Is it just me, or is this NP-hard? – David Titarenco (from comment)

If you want LCS of arbitrary number of strings its NP-hard. But it the number of input strings is constant ( as in this case, 2) this can be done in polynomial time.

edited Sep 20, 2010 at 3:27

answered Sep 20, 2010 at 3:19

codaddict

457k83 gold badges501 silver badges537 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

aaronasterling Over a year ago

This isn't right. given OP's example input, it would return 'ABCDFG'

codaddict Over a year ago

@Aaron: You'll have to modify the algorithm a bit to find the actual substring that contributed to the answer. But the basic idea remains very much the same.

Peter Chang Over a year ago

Thanks, I'll look into modifying an LCS algo

Collectives™ on Stack Overflow

Finding partial substrings within a string

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related