Why Longest Common Substring in DSA Typescript?

The Big Idea

Discover how to find the longest matching part between two texts without endless guessing!

The Scenario

Imagine you have two long texts and you want to find the longest part that appears exactly the same in both. Doing this by reading and comparing every possible part by hand would take forever!

The Problem

Manually checking every possible substring is slow and confusing. You might miss some matches or spend hours comparing parts that don't match. It's easy to make mistakes and waste time.

The Solution

The Longest Common Substring method quickly finds the longest matching part between two texts by using a smart way to compare all parts at once. It saves time and avoids mistakes.

Before vs After

✗ Before

function findLongestCommonSubstringManual(text1: string, text2: string): string {
  let longest = '';
  for (let i = 0; i < text1.length; i++) {
    for (let j = 0; j < text2.length; j++) {
      let k = 0;
      while (i + k < text1.length && j + k < text2.length && text1[i + k] === text2[j + k]) {
        k++;
      }
      if (k > longest.length) {
        longest = text1.substring(i, i + k);
      }
    }
  }
  return longest;
}

✓ After

function longestCommonSubstring(text1: string, text2: string): string {
  const dp: number[][] = Array(text1.length + 1).fill(0).map(() => Array(text2.length + 1).fill(0));
  let maxLength = 0;
  let endIndex = 0;
  for (let i = 1; i <= text1.length; i++) {
    for (let j = 1; j <= text2.length; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
        if (dp[i][j] > maxLength) {
          maxLength = dp[i][j];
          endIndex = i;
        }
      }
    }
  }
  return text1.substring(endIndex - maxLength, endIndex);
}

What It Enables

This lets you quickly find the longest exact matching part between two texts, which helps in many areas like spell checking, DNA analysis, and plagiarism detection.

Real Life Example

When checking if two documents share a copied paragraph, the Longest Common Substring helps find the longest copied section automatically, saving hours of manual reading.

Key Takeaways

Manual comparison is slow and error-prone.

Longest Common Substring uses a smart table to find matches fast.

This method helps in text analysis, biology, and more.