最長的常見子序列替代

Question

我想問你關於LCS算法的任何替代方案。

我LCS算法在JavaScript系統的實現，以及它的工作原理如下圖所示

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

，但我正在尋找算法顯示兩個串的唯一共同的部分，所以從function(string_A, string_B)結果應該是london。

Answer 1

實際上，這個算法似乎有點太具體只是嚴格捕獲公共子串。它可能比你的情況需要更靈活。它捕獲從string_A是發生在同一順序string_B，無論是否有其他與符號的所有符號：

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

只提取嚴格的公共部分，該解決方案可以說是相當明顯的。只需測試string_B所有可能的子字符串即可包含在string_A中，從最長開始。因此，我建議我自己的版本：

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; 
} 

嘗試它的工作：http://codepen.io/pttsky/pen/rjbOza