หา Longest Common Substring ระหว่างสองสตริงใน JavaScript

Longest Common Substring

หา Substring (ติดกัน) ที่ยาวที่สุดซึ่งปรากฏในทั้งสองสตริง ต่างจาก LCS (Subsequence) ที่ไม่ต้องติดกัน

ตัวอย่าง

const str1 = 'ABABC';
const str2 = 'BABCA';

Common Substrings: "BAB", "ABC", "BABC" → ยาวที่สุด = "BABC"

โค้ดตัวอย่าง (Dynamic Programming)

const str1 = 'ABABC';
const str2 = 'BABCA';

const findCommon = (str1 = '', str2 = '') => {
  const s1 = [...str1];
  const s2 = [...str2];
  
  // DP Table: (s2.length+1) x (s1.length+1)
  const arr = Array(s2.length + 1).fill(null).map(() => 
    Array(s1.length + 1).fill(null));
  
  // Initialize
  for (let j = 0; j <= s1.length; j++) arr[0][j] = 0;
  for (let i = 0; i <= s2.length; i++) arr[i][0] = 0;
  
  let len = 0; // ความยาวสูงสุด
  let col = 0, row = 0; // ตำแหน่งสิ้นสุด
  
  // Fill DP table
  for (let i = 1; i <= s2.length; i++) {
    for (let j = 1; j <= s1.length; j++) {
      if (s1[j - 1] === s2[i - 1]) {
        arr[i][j] = arr[i - 1][j - 1] + 1;
      } else {
        arr[i][j] = 0; // ต้องติดกัน → รีเซ็ตเป็น 0
      }
      
      // Track maximum
      if (arr[i][j] > len) {
        len = arr[i][j];
        col = j;
        row = i;
      }
    }
  }
  
  if (len === 0) return '';
  
  // Reconstruct substring
  let res = '';
  while (arr[row][col] > 0) {
    res = s1[col - 1] + res;
    row--; col--;
  }
  return res;
};

console.log(findCommon(str1, str2));

ผลลัพธ์

BABC

ความแตกต่าง LCS vs LCSubstring

ความซับซ้อน

• Time: O(m × n)
• Space: O(m × n) → สามารถลดเป็น O(min(m,n)) ได้

โค้ดประหยัดหน่วยความจำ (O(min(m,n)) Space)

const lcsSubstringOptimized = (str1, str2) => {
  // ให้ str1 สั้นกว่า
  if (str1.length > str2.length) [str1, str2] = [str2, str1];
  
  const prev = new Array(str1.length + 1).fill(0);
  let maxLen = 0, endIdx = 0;
  
  for (let i = 1; i <= str2.length; i++) {
    const curr = new Array(str1.length + 1).fill(0);
    for (let j = 1; j <= str1.length; j++) {
      if (str1[j-1] === str2[i-1]) {
        curr[j] = prev[j-1] + 1;
        if (curr[j] > maxLen) {
          maxLen = curr[j];
          endIdx = j;
        }
      }
    }
    // ไม่ต้อง copy array, สลับ reference
    // prev = curr; // แต่ต้องสร้าง curr ใหม่ทุก loop
  }
  return str1.slice(endIdx - maxLen, endIdx);
};

Suffix Array / Suffix Tree (Advanced)

สำหรับสตริงยาวมาก (DNA sequences) ใช้ Suffix Array/Tree ได้ O(n log n) หรือ O(n)