CODEWITHSUNDEEP
javascript
Peter Crauch
Peter Crauch

Reputation: 45

Longest common subsequence alternative

I would like to ask you about to any alternatives for LCS algorithm.

I have an implemention of LCS algorithm in javascript, and it works like below

string_A: 'hello from london sample'
string_B: 'londons'
result: 'londons'

but I am looking for algorithm which shows only common part of two strings, so result from function(string_A, string_B) should be london.

Upvotes: 0

Views: 1843

Answers (1)

pttsky
pttsky

Reputation: 757

Actually, this algorithm seems a bit too specific to just capture common substring strictly. It is likely more flexible than your situation requires. It captures all symbols from string_A that take place in the same order in string_B, no matter if there are other symbols between:

LCS( 'hello from london sample', 'hfls' ); // returns 'hlfs'
LCS( 'hello from london sample', 'from amazing london' ); // returns 'from london'

To extract just strictly the common part, the solution can be quite obvious. Just test all possible substrings of string_B to be included in string_A, starting from the longest. So I suggest my own version:

function LCSS( a, b ) {
    let len = b.length, originalLen = b.length;
    do {
        for ( let i = 0; i <= originalLen - len; i++ ) {
            let needle = b.substr( i, len );
            if ( a.indexOf( needle ) !== -1 ) return needle;
        }
    } while ( len-- > 0 );
    return false;
}

Try it working: http://codepen.io/pttsky/pen/rjbOza

Upvotes: 1

Related Questions