Longest Common Subsequence

Gives the longest common substring between two stings.

Description

%%%INPUT
%%%X, Y - both are strings e.g. 'test' or 'stingtocompare'
%%%OUTPUT
%%%D is the substring over the length of the shortest string
%%%dist is the length of the substring
%%%aLongestString is a sting of length dist (only one of potentially many)

• MATLAB release: MATLAB 7.3 (R2006b)

[Bruno Luong]

Code seems Buggy, even for the example provided

>> X='test', Y='stingtocompare'

X =

test

Y =

stingtocompare

>> [D, dist, aLongestString] = LCS(X,Y)
??? Attempted to access b(2,0); index must be a positive integer or logical.

Error in ==> LCS at 55
    if(b(i,j) == 3)
 
>>

[Matt Fig]

Something is still wrong.

[D,G,S] = LCS('fbce','abcde');S
S =
bce

[Bruno Luong]

I still do not function understand what the function does:

X = [ 8 8 9 3 7 1 2 4 5 1 ]
Y = [ 7 6 6 10 2 7 9 4 1 1]

[D, dist, aLongestString] = LCS(X,Y)
D = 0.6000
dist = 4
aLongestString = [ 7 2 4 1]

% Furthermore what is the limit of the function?

>> X=ceil(10*rand(1,1e4));
>> Y=ceil(10*rand(1,1e4));
>> [D, dist, aLongestString] = LCS(X,Y)
??? Out of memory. Type HELP MEMORY for your options.

Error in ==> LCS at 20
b = zeros(n+1,m+1);
  

[David Cumin]

Bruno,
Thanks for your comments. The LCS('fbce','abcde'); gives the right answer. The code is designed to find the longest common substring of two given inputs. In this example, both 'fbce' and 'abcde' contain 'bce':
fbce -> '-bce'
'abcde' -> '-bc-e'
Hope that makes sense.

The technique is common to pattern matching techniques. I'm not sure of the limit to the function. I guess it depends on memory.

Cheers,
David

[Bruno Luong]

Thank you, I see now. I suggest to update the help and describe more clearly what function does. It is also good if you could add few words about memory requirement/complexity and algorithm.

[Bruno Luong]