Longest Common Substring چیست؟ پیدا کردن طولانی‌ترین بخش مشترک دو رشته با Dynamic Programming

Longest Common Substring یکی از مسائل کلاسیک String Algorithms است که هدف آن پیدا کردن طولانی‌ترین بخش پیوسته مشترک میان دو رشته است.

کلمه مهم در این تعریف، پیوسته یا Contiguous بودن است.

برای مثال دو رشته زیر را در نظر بگیرید:

Code

ABABC
BABCA

بخش مشترک:

Code

BABC

در هر دو رشته به صورت پیوسته وجود دارد.

بنابراین:

Code

Longest Common Substring = "BABC"
Length = 4

این مسئله در نگاه اول ساده به نظر می‌رسد، اما تفاوت مهمی با مسئله معروف Longest Common Subsequence یا LCS دارد.

Substring چیست؟

Substring بخشی از یک رشته است که کاراکترهای آن باید پشت سر هم باشند.

برای رشته:

Code

ABCDE

موارد زیر Substring هستند:

Code

ABC
BCD
DE
C

اما:

Code

ACE

Substring نیست، زیرا کاراکترها در رشته اصلی پشت سر هم نیستند.

یک مثال ساده

دو رشته زیر را داریم:

Code

String 1: programming
String 2: gaming

یکی از بخش‌های مشترک مهم:

Code

ming

است.

این چهار کاراکتر در انتهای هر دو رشته به صورت پیوسته ظاهر شده‌اند.

در نتیجه:

Code

Longest Common Substring = "ming"
Length = 4

روش Brute Force

ساده‌ترین راه این است که تمام Substringهای رشته اول را تولید کنیم و بررسی کنیم کدام‌یک در رشته دوم وجود دارند.

یک رشته با طول n تقریباً:

Code

n × (n + 1) / 2

Substring دارد.

اگر هرکدام را نیز در رشته دوم جستجو کنیم، هزینه محاسباتی می‌تواند به سرعت زیاد شود.

این روش برای ورودی‌های کوچک قابل استفاده است، اما برای داده‌های بزرگ انتخاب مناسبی نیست.

استفاده از Dynamic Programming

روش کلاسیک برای حل این مسئله استفاده از Dynamic Programming است.

فرض کنید دو رشته داریم:

Code

a
b

تعریف می‌کنیم:

Code

dp[i][j]

برابر باشد با طول Longest Common Substring که دقیقاً در موقعیت i - 1 از رشته اول و j - 1 از رشته دوم پایان پیدا می‌کند.

این قسمت از تعریف بسیار مهم است.

رابطه اصلی DP

اگر دو کاراکتر برابر باشند:

Code

a[i - 1] === b[j - 1]

می‌توانیم Substring قبلی را یک کاراکتر ادامه دهیم:

Code

dp[i][j] = dp[i - 1][j - 1] + 1

اما اگر متفاوت باشند:

Code

dp[i][j] = 0

چرا صفر؟

چون Substring باید پیوسته باشد. یک mismatch زنجیره پیوستگی را قطع می‌کند.

این مهم‌ترین تفاوت با Longest Common Subsequence است.

مثال مرحله‌به‌مرحله

فرض کنید:

Code

a = "ABABC"
b = "BABCA"

جدول DP به صورت مفهومی چنین خواهد بود:

Code

      B  A  B  C  A
A     0  1  0  0  1
B     1  0  2  0  0
A     0  2  0  0  1
B     1  0  3  0  0
C     0  0  0  4  0

بزرگ‌ترین عدد موجود در جدول:

Code

است.

این مقدار در کاراکتر C پایان یافته و Substring متناظر:

Code

BABC

است.

چرا فقط بزرگ‌ترین مقدار جدول را پیدا می‌کنیم؟

برخلاف بعضی مسائل Dynamic Programming، پاسخ الزاماً در آخرین Cell جدول قرار ندارد.

برای مثال ممکن است Longest Common Substring در وسط دو رشته تمام شود.

بنابراین هنگام پر کردن جدول باید یک متغیر مانند:

Code

maxLength

نگه داریم و بزرگ‌ترین مقدار دیده‌شده را ذخیره کنیم.

پیاده‌سازی ساده با TypeScript

TypeScript

function longestCommonSubstringLength(
  a: string,
  b: string
): number {
  const dp: number[][] = Array.from(
    { length: a.length + 1 },
    () => new Array(b.length + 1).fill(0)
  );

  let maxLength = 0;

  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
        maxLength = Math.max(maxLength, dp[i][j]);
      } else {
        dp[i][j] = 0;
      }
    }
  }

  return maxLength;
}

console.log(
  longestCommonSubstringLength("ABABC", "BABCA")
); // 4

برگرداندن خود Substring

در بسیاری از مسائل فقط طول کافی نیست و می‌خواهیم خود رشته مشترک را نیز پیدا کنیم.

برای این کار علاوه بر maxLength، موقعیت پایان بهترین Match را نیز ذخیره می‌کنیم.

TypeScript

function longestCommonSubstring(
  a: string,
  b: string
): string {
  const dp: number[][] = Array.from(
    { length: a.length + 1 },
    () => new Array(b.length + 1).fill(0)
  );

  let maxLength = 0;
  let endIndex = 0;

  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;

        if (dp[i][j] > maxLength) {
          maxLength = dp[i][j];
          endIndex = i;
        }
      }
    }
  }

  return a.slice(endIndex - maxLength, endIndex);
}

console.log(
  longestCommonSubstring("ABABC", "BABCA")
); // BABC

پیچیدگی زمانی و فضایی

اگر طول رشته اول n و طول رشته دوم m باشد:

Code

Time Complexity: O(n × m)
Space Complexity: O(n × m)

زیرا برای هر ترکیب از موقعیت‌های دو رشته یک Cell محاسبه می‌کنیم.

بهینه‌سازی حافظه

برای محاسبه Row فعلی فقط به Row قبلی نیاز داریم.

بنابراین می‌توانیم فضای حافظه را از:

Code

O(n × m)

به:

Code

O(m)

یا دقیق‌تر:

Code

O(min(n, m))

کاهش دهیم.

نمونه:

TypeScript

function longestCommonSubstringOptimized(
  a: string,
  b: string
): number {
  if (b.length > a.length) {
    [a, b] = [b, a];
  }

  let previous = new Array(b.length + 1).fill(0);
  let maxLength = 0;

  for (let i = 1; i <= a.length; i++) {
    const current = new Array(b.length + 1).fill(0);

    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        current[j] = previous[j - 1] + 1;
        maxLength = Math.max(maxLength, current[j]);
      }
    }

    previous = current;
  }

  return maxLength;
}

Longest Common Substring و Longest Common Subsequence چه تفاوتی دارند؟

این دو نام بسیار شبیه‌اند و یکی از رایج‌ترین اشتباهات در مسائل الگوریتمی همین است.

فرض کنید:

Code

a = "ABCDEF"
b = "ACEF"

Longest Common Subsequence

می‌تواند باشد:

Code

ACEF

زیرا لازم نیست کاراکترها کنار هم باشند؛ فقط ترتیب باید حفظ شود.

اما Longest Common Substring باید پیوسته باشد.

در این مثال یکی از Substringهای مشترک:

Code

EF

است.

بنابراین:

Code

Longest Common Subsequence ≠ Longest Common Substring

تفاوت در رابطه DP

برای Longest Common Substring، هنگام mismatch داریم:

Code

dp[i][j] = 0

اما در LCS معمولاً داریم:

Code

dp[i][j] = max(
  dp[i - 1][j],
  dp[i][j - 1]
)

همین تفاوت کوچک نشان‌دهنده تفاوت بنیادی دو مسئله است.

کاربرد در تشخیص شباهت متن

فرض کنید دو رشته داریم:

Code

customer_relationship_management
relationship_manager

وجود بخش مشترک بزرگی مانند:

Code

relationship_manag

می‌تواند نشان دهد دو رشته دارای بخش محتوایی مشترک قابل توجهی هستند.

البته Longest Common Substring به تنهایی معیار کامل Similarity نیست، اما می‌تواند یکی از Featureها باشد.

کاربرد در Data Deduplication

در سیستم‌های CRM، Data Cleaning یا Import ممکن است داده‌هایی داشته باشیم که بخشی از آن‌ها مشترک است.

مثلاً:

Code

Arian Soleimanzadeh Software Engineer
Arian Soleimanzadeh

یک Substring مشترک طولانی می‌تواند یکی از Signalهای تشخیص ارتباط دو Record باشد.

در سیستم واقعی باید این معیار را با مواردی مانند:

Levenshtein Distance
Exact Email Match
Phone Match
Token Similarity
Normalization

ترکیب کنیم.

کاربرد در Bioinformatics

Sequenceهای DNA یا Protein را می‌توان مانند رشته‌ها در نظر گرفت.

برای مثال:

Code

ACGTACGT
TTGTACGG

یک بخش مشترک پیوسته مانند:

Code

GTACG

می‌تواند نشان‌دهنده یک ناحیه مشابه میان Sequenceها باشد.

البته Bioinformatics واقعی معمولاً از الگوریتم‌های تخصصی‌تر Sequence Alignment نیز استفاده می‌کند.

کاربرد در Version Comparison

فرض کنید دو نسخه از یک متن یا Config داریم.

Code

version 1:
/api/v1/customer/profile

version 2:
/api/v2/customer/profile

بخش:

Code

/customer/profile

مشترک است.

Longest Common Substring می‌تواند در بعضی مسائل مقایسه Versionها یا Sequenceها به عنوان یک Building Block استفاده شود.

کاربرد در Plagiarism Detection

یکی از ایده‌های ابتدایی برای پیدا کردن بخش‌های کپی‌شده میان دو متن، بررسی Segmentهای مشترک طولانی است.

اگر دو Document دارای چندین Substring بلند و یکسان باشند، می‌تواند یک Signal برای Similarity باشد.

البته سیستم‌های واقعی Plagiarism Detection بسیار پیچیده‌تر هستند و معمولاً از Tokenization، Fingerprinting، N-grams و Semantic Similarity نیز استفاده می‌کنند.

کاربرد در Log و Security Analysis

گاهی لازم است قسمت‌های مشترک میان چند Log Entry یا Payload بررسی شوند.

مثلاً:

Code

ERROR_AUTH_TOKEN_EXPIRED_USER_101
ERROR_AUTH_TOKEN_EXPIRED_USER_205

بخش مشترک بزرگی مانند:

Code

ERROR_AUTH_TOKEN_EXPIRED_USER_

می‌تواند به تشخیص Patternهای مشابه کمک کند.

آیا می‌توان چند جواب صحیح داشت؟

بله.

ممکن است دو یا چند Substring با طول برابر بیشینه وجود داشته باشند.

برای مثال:

Code

a = "abcXYZ123"
b = "abcABC123"

دو Substring مشترک داریم:

Code

abc
123

که هر دو طول 3 دارند.

اگر فقط یک جواب لازم باشد، معمولاً اولین یا آخرین Match را برمی‌گردانیم.

اگر همه جواب‌ها لازم باشند باید End Index تمام Cellهایی را که مقدارشان برابر maxLength است نگه داریم.

Edge Caseها

یکی از رشته‌ها خالی باشد

Code

"hello"
""

پاسخ:

Code

Length = 0

هیچ کاراکتر مشترکی وجود نداشته باشد

Python

abc
def

پاسخ:

Code

دو رشته کاملاً برابر باشند

Code

algorithm
algorithm

کل رشته پاسخ است.

تفاوت حروف بزرگ و کوچک

Code

Hello
hello

در مقایسه استاندارد H و h متفاوت هستند.

اگر Case-insensitive Search نیاز باشد، قبل از الگوریتم باید Normalization انجام شود.

یک سؤال رایج مصاحبه

صورت مسئله معمولاً به این شکل است:

دو String داده شده است. طول یا خود Longest Common Substring آن‌ها را پیدا کنید.

یک جواب خوب باید شامل این نکات باشد:

تعریف صحیح Substring و پیوستگی.
تعریف dp[i][j].
Reset کردن مقدار به صفر هنگام mismatch.
نگه داشتن maxLength.
تحلیل پیچیدگی O(n × m).
در صورت نیاز، توضیح Space Optimization.

اشتباه رایج: استفاده از منطق LCS

رایج‌ترین اشتباه این است که هنگام mismatch بنویسیم:

Code

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

این رابطه مربوط به Longest Common Subsequence است.

برای Substring باید زنجیره قطع شود:

Code

dp[i][j] = 0

زیرا دیگر Match پیوسته نیست.

آیا الگوریتم سریع‌تری وجود دارد؟

بله. برای ورودی‌های بسیار بزرگ می‌توان از ساختارها و الگوریتم‌های پیشرفته‌تری مانند:

Suffix Tree
Suffix Array
Suffix Automaton

استفاده کرد.

برخی از این روش‌ها می‌توانند مسئله را با پیچیدگی زمانی بسیار بهتر حل کنند، اما پیاده‌سازی و درک آن‌ها پیچیده‌تر است.

برای بسیاری از مسائل آموزشی، مصاحبه‌ای و ورودی‌های متوسط، روش Dynamic Programming انتخابی واضح و قابل فهم است.

جمع‌بندی

Longest Common Substring طولانی‌ترین بخش پیوسته مشترک میان دو رشته را پیدا می‌کند.

رابطه اصلی آن بسیار ساده است:

Code

if a[i - 1] === b[j - 1]
    dp[i][j] = dp[i - 1][j - 1] + 1
else
    dp[i][j] = 0

پیچیدگی نسخه کلاسیک:

Code

Time Complexity:  O(n × m)
Space Complexity: O(n × m)

و با بهینه‌سازی حافظه:

Code

Space Complexity: O(min(n, m))

مهم‌ترین نکته برای به خاطر سپردن این است:

در Longest Common Substring، Match باید بدون وقفه ادامه پیدا کند؛ یک mismatch طول زنجیره فعلی را به صفر برمی‌گرداند.

همین ویژگی آن را از Longest Common Subsequence متمایز می‌کند.

کلمه مهم در این تعریف، پیوسته یا Contiguous بودن است.

برای مثال دو رشته زیر را در نظر بگیرید:

Code

ABABC
BABCA

بخش مشترک:

Code

BABC

در هر دو رشته به صورت پیوسته وجود دارد.

بنابراین:

Code

Longest Common Substring = "BABC"
Length = 4

این مسئله در نگاه اول ساده به نظر می‌رسد، اما تفاوت مهمی با مسئله معروف Longest Common Subsequence یا LCS دارد.

Substring چیست؟

Substring بخشی از یک رشته است که کاراکترهای آن باید پشت سر هم باشند.

برای رشته:

Code

ABCDE

موارد زیر Substring هستند:

Code

ABC
BCD
DE
C

اما:

Code

ACE

Substring نیست، زیرا کاراکترها در رشته اصلی پشت سر هم نیستند.

یک مثال ساده

دو رشته زیر را داریم:

Code

String 1: programming
String 2: gaming

یکی از بخش‌های مشترک مهم:

Code

ming

است.

این چهار کاراکتر در انتهای هر دو رشته به صورت پیوسته ظاهر شده‌اند.

در نتیجه:

Code

Longest Common Substring = "ming"
Length = 4

روش Brute Force

ساده‌ترین راه این است که تمام Substringهای رشته اول را تولید کنیم و بررسی کنیم کدام‌یک در رشته دوم وجود دارند.

یک رشته با طول n تقریباً:

Code

n × (n + 1) / 2

Substring دارد.

اگر هرکدام را نیز در رشته دوم جستجو کنیم، هزینه محاسباتی می‌تواند به سرعت زیاد شود.

این روش برای ورودی‌های کوچک قابل استفاده است، اما برای داده‌های بزرگ انتخاب مناسبی نیست.

استفاده از Dynamic Programming

روش کلاسیک برای حل این مسئله استفاده از Dynamic Programming است.

فرض کنید دو رشته داریم:

Code

a
b

تعریف می‌کنیم:

Code

dp[i][j]

برابر باشد با طول Longest Common Substring که دقیقاً در موقعیت i - 1 از رشته اول و j - 1 از رشته دوم پایان پیدا می‌کند.

این قسمت از تعریف بسیار مهم است.

رابطه اصلی DP

اگر دو کاراکتر برابر باشند:

Code

a[i - 1] === b[j - 1]

می‌توانیم Substring قبلی را یک کاراکتر ادامه دهیم:

Code

dp[i][j] = dp[i - 1][j - 1] + 1

اما اگر متفاوت باشند:

Code

dp[i][j] = 0

چرا صفر؟

چون Substring باید پیوسته باشد. یک mismatch زنجیره پیوستگی را قطع می‌کند.

این مهم‌ترین تفاوت با Longest Common Subsequence است.

مثال مرحله‌به‌مرحله

فرض کنید:

Code

a = "ABABC"
b = "BABCA"

جدول DP به صورت مفهومی چنین خواهد بود:

Code

      B  A  B  C  A
A     0  1  0  0  1
B     1  0  2  0  0
A     0  2  0  0  1
B     1  0  3  0  0
C     0  0  0  4  0

بزرگ‌ترین عدد موجود در جدول:

Code

است.

این مقدار در کاراکتر C پایان یافته و Substring متناظر:

Code

BABC

است.

چرا فقط بزرگ‌ترین مقدار جدول را پیدا می‌کنیم؟

برخلاف بعضی مسائل Dynamic Programming، پاسخ الزاماً در آخرین Cell جدول قرار ندارد.

برای مثال ممکن است Longest Common Substring در وسط دو رشته تمام شود.

بنابراین هنگام پر کردن جدول باید یک متغیر مانند:

Code

maxLength

نگه داریم و بزرگ‌ترین مقدار دیده‌شده را ذخیره کنیم.

پیاده‌سازی ساده با TypeScript

TypeScript

function longestCommonSubstringLength(
  a: string,
  b: string
): number {
  const dp: number[][] = Array.from(
    { length: a.length + 1 },
    () => new Array(b.length + 1).fill(0)
  );

  let maxLength = 0;

  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
        maxLength = Math.max(maxLength, dp[i][j]);
      } else {
        dp[i][j] = 0;
      }
    }
  }

  return maxLength;
}

console.log(
  longestCommonSubstringLength("ABABC", "BABCA")
); // 4

برگرداندن خود Substring

در بسیاری از مسائل فقط طول کافی نیست و می‌خواهیم خود رشته مشترک را نیز پیدا کنیم.

برای این کار علاوه بر maxLength، موقعیت پایان بهترین Match را نیز ذخیره می‌کنیم.

TypeScript

function longestCommonSubstring(
  a: string,
  b: string
): string {
  const dp: number[][] = Array.from(
    { length: a.length + 1 },
    () => new Array(b.length + 1).fill(0)
  );

  let maxLength = 0;
  let endIndex = 0;

  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;

        if (dp[i][j] > maxLength) {
          maxLength = dp[i][j];
          endIndex = i;
        }
      }
    }
  }

  return a.slice(endIndex - maxLength, endIndex);
}

console.log(
  longestCommonSubstring("ABABC", "BABCA")
); // BABC

پیچیدگی زمانی و فضایی

اگر طول رشته اول n و طول رشته دوم m باشد:

Code

Time Complexity: O(n × m)
Space Complexity: O(n × m)

زیرا برای هر ترکیب از موقعیت‌های دو رشته یک Cell محاسبه می‌کنیم.

بهینه‌سازی حافظه

برای محاسبه Row فعلی فقط به Row قبلی نیاز داریم.

بنابراین می‌توانیم فضای حافظه را از:

Code

O(n × m)

به:

Code

O(m)

یا دقیق‌تر:

Code

O(min(n, m))

کاهش دهیم.

نمونه:

TypeScript

function longestCommonSubstringOptimized(
  a: string,
  b: string
): number {
  if (b.length > a.length) {
    [a, b] = [b, a];
  }

  let previous = new Array(b.length + 1).fill(0);
  let maxLength = 0;

  for (let i = 1; i <= a.length; i++) {
    const current = new Array(b.length + 1).fill(0);

    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        current[j] = previous[j - 1] + 1;
        maxLength = Math.max(maxLength, current[j]);
      }
    }

    previous = current;
  }

  return maxLength;
}

Longest Common Substring و Longest Common Subsequence چه تفاوتی دارند؟

این دو نام بسیار شبیه‌اند و یکی از رایج‌ترین اشتباهات در مسائل الگوریتمی همین است.

فرض کنید:

Code

a = "ABCDEF"
b = "ACEF"

Longest Common Subsequence

می‌تواند باشد:

Code

ACEF

زیرا لازم نیست کاراکترها کنار هم باشند؛ فقط ترتیب باید حفظ شود.

اما Longest Common Substring باید پیوسته باشد.

در این مثال یکی از Substringهای مشترک:

Code

EF

است.

بنابراین:

Code

Longest Common Subsequence ≠ Longest Common Substring

تفاوت در رابطه DP

برای Longest Common Substring، هنگام mismatch داریم:

Code

dp[i][j] = 0

اما در LCS معمولاً داریم:

Code

dp[i][j] = max(
  dp[i - 1][j],
  dp[i][j - 1]
)

همین تفاوت کوچک نشان‌دهنده تفاوت بنیادی دو مسئله است.

کاربرد در تشخیص شباهت متن

فرض کنید دو رشته داریم:

Code

customer_relationship_management
relationship_manager

وجود بخش مشترک بزرگی مانند:

Code

relationship_manag

می‌تواند نشان دهد دو رشته دارای بخش محتوایی مشترک قابل توجهی هستند.

البته Longest Common Substring به تنهایی معیار کامل Similarity نیست، اما می‌تواند یکی از Featureها باشد.

کاربرد در Data Deduplication

در سیستم‌های CRM، Data Cleaning یا Import ممکن است داده‌هایی داشته باشیم که بخشی از آن‌ها مشترک است.

مثلاً:

Code

Arian Soleimanzadeh Software Engineer
Arian Soleimanzadeh

یک Substring مشترک طولانی می‌تواند یکی از Signalهای تشخیص ارتباط دو Record باشد.

در سیستم واقعی باید این معیار را با مواردی مانند:

Levenshtein Distance
Exact Email Match
Phone Match
Token Similarity
Normalization

ترکیب کنیم.

کاربرد در Bioinformatics

Sequenceهای DNA یا Protein را می‌توان مانند رشته‌ها در نظر گرفت.

برای مثال:

Code

ACGTACGT
TTGTACGG

یک بخش مشترک پیوسته مانند:

Code

GTACG

می‌تواند نشان‌دهنده یک ناحیه مشابه میان Sequenceها باشد.

البته Bioinformatics واقعی معمولاً از الگوریتم‌های تخصصی‌تر Sequence Alignment نیز استفاده می‌کند.

کاربرد در Version Comparison

فرض کنید دو نسخه از یک متن یا Config داریم.

Code

version 1:
/api/v1/customer/profile

version 2:
/api/v2/customer/profile

بخش:

Code

/customer/profile

مشترک است.

Longest Common Substring می‌تواند در بعضی مسائل مقایسه Versionها یا Sequenceها به عنوان یک Building Block استفاده شود.

کاربرد در Plagiarism Detection

یکی از ایده‌های ابتدایی برای پیدا کردن بخش‌های کپی‌شده میان دو متن، بررسی Segmentهای مشترک طولانی است.

اگر دو Document دارای چندین Substring بلند و یکسان باشند، می‌تواند یک Signal برای Similarity باشد.

کاربرد در Log و Security Analysis

گاهی لازم است قسمت‌های مشترک میان چند Log Entry یا Payload بررسی شوند.

مثلاً:

Code

ERROR_AUTH_TOKEN_EXPIRED_USER_101
ERROR_AUTH_TOKEN_EXPIRED_USER_205

بخش مشترک بزرگی مانند:

Code

ERROR_AUTH_TOKEN_EXPIRED_USER_

می‌تواند به تشخیص Patternهای مشابه کمک کند.

آیا می‌توان چند جواب صحیح داشت؟

بله.

ممکن است دو یا چند Substring با طول برابر بیشینه وجود داشته باشند.

برای مثال:

Code

a = "abcXYZ123"
b = "abcABC123"

دو Substring مشترک داریم:

Code

abc
123

که هر دو طول 3 دارند.

اگر فقط یک جواب لازم باشد، معمولاً اولین یا آخرین Match را برمی‌گردانیم.

اگر همه جواب‌ها لازم باشند باید End Index تمام Cellهایی را که مقدارشان برابر maxLength است نگه داریم.

Edge Caseها

یکی از رشته‌ها خالی باشد

Code

"hello"
""

پاسخ:

Code

Length = 0

هیچ کاراکتر مشترکی وجود نداشته باشد

Python

abc
def

پاسخ:

Code

دو رشته کاملاً برابر باشند

Code

algorithm
algorithm

کل رشته پاسخ است.

تفاوت حروف بزرگ و کوچک

Code

Hello
hello

در مقایسه استاندارد H و h متفاوت هستند.

اگر Case-insensitive Search نیاز باشد، قبل از الگوریتم باید Normalization انجام شود.

یک سؤال رایج مصاحبه

صورت مسئله معمولاً به این شکل است:

دو String داده شده است. طول یا خود Longest Common Substring آن‌ها را پیدا کنید.

یک جواب خوب باید شامل این نکات باشد:

تعریف صحیح Substring و پیوستگی.
تعریف dp[i][j].
Reset کردن مقدار به صفر هنگام mismatch.
نگه داشتن maxLength.
تحلیل پیچیدگی O(n × m).
در صورت نیاز، توضیح Space Optimization.

اشتباه رایج: استفاده از منطق LCS

رایج‌ترین اشتباه این است که هنگام mismatch بنویسیم:

Code

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

این رابطه مربوط به Longest Common Subsequence است.

برای Substring باید زنجیره قطع شود:

Code

dp[i][j] = 0

زیرا دیگر Match پیوسته نیست.

آیا الگوریتم سریع‌تری وجود دارد؟

بله. برای ورودی‌های بسیار بزرگ می‌توان از ساختارها و الگوریتم‌های پیشرفته‌تری مانند:

Suffix Tree
Suffix Array
Suffix Automaton

استفاده کرد.

برای بسیاری از مسائل آموزشی، مصاحبه‌ای و ورودی‌های متوسط، روش Dynamic Programming انتخابی واضح و قابل فهم است.

جمع‌بندی

Longest Common Substring طولانی‌ترین بخش پیوسته مشترک میان دو رشته را پیدا می‌کند.

رابطه اصلی آن بسیار ساده است:

Code

if a[i - 1] === b[j - 1]
    dp[i][j] = dp[i - 1][j - 1] + 1
else
    dp[i][j] = 0

پیچیدگی نسخه کلاسیک:

Code

Time Complexity:  O(n × m)
Space Complexity: O(n × m)

و با بهینه‌سازی حافظه:

Code

Space Complexity: O(min(n, m))

مهم‌ترین نکته برای به خاطر سپردن این است:

در Longest Common Substring، Match باید بدون وقفه ادامه پیدا کند؛ یک mismatch طول زنجیره فعلی را به صفر برمی‌گرداند.

همین ویژگی آن را از Longest Common Subsequence متمایز می‌کند.

Longest Common Substring چیست؟ پیدا کردن طولانی‌ترین بخش مشترک دو رشته با Dynamic Programming

Substring چیست؟

یک مثال ساده

روش Brute Force

استفاده از Dynamic Programming

رابطه اصلی DP

مثال مرحله‌به‌مرحله

چرا فقط بزرگ‌ترین مقدار جدول را پیدا می‌کنیم؟

پیاده‌سازی ساده با TypeScript

برگرداندن خود Substring

پیچیدگی زمانی و فضایی

بهینه‌سازی حافظه

Longest Common Substring و Longest Common Subsequence چه تفاوتی دارند؟

Longest Common Subsequence

تفاوت در رابطه DP

کاربرد در تشخیص شباهت متن

کاربرد در Data Deduplication

کاربرد در Bioinformatics

کاربرد در Version Comparison

کاربرد در Plagiarism Detection

کاربرد در Log و Security Analysis

آیا می‌توان چند جواب صحیح داشت؟

Edge Caseها

یکی از رشته‌ها خالی باشد

هیچ کاراکتر مشترکی وجود نداشته باشد

دو رشته کاملاً برابر باشند

تفاوت حروف بزرگ و کوچک

یک سؤال رایج مصاحبه

اشتباه رایج: استفاده از منطق LCS

آیا الگوریتم سریع‌تری وجود دارد؟

جمع‌بندی

الگوریتم Kosaraju چیست و اصلاً چه مشکلی را حل می‌کند؟

Palindrome چیست؟ آموزش تشخیص رشته‌های قرینه با Two Pointers و TypeScript

Longest Common Substring چیست؟ پیدا کردن طولانی‌ترین بخش مشترک دو رشته با Dynamic Programming

Substring چیست؟

یک مثال ساده

روش Brute Force

استفاده از Dynamic Programming

رابطه اصلی DP

مثال مرحله‌به‌مرحله

چرا فقط بزرگ‌ترین مقدار جدول را پیدا می‌کنیم؟

پیاده‌سازی ساده با TypeScript

برگرداندن خود Substring

پیچیدگی زمانی و فضایی

بهینه‌سازی حافظه

Longest Common Substring و Longest Common Subsequence چه تفاوتی دارند؟

Longest Common Subsequence

تفاوت در رابطه DP

کاربرد در تشخیص شباهت متن

کاربرد در Data Deduplication

کاربرد در Bioinformatics

کاربرد در Version Comparison

کاربرد در Plagiarism Detection

کاربرد در Log و Security Analysis

آیا می‌توان چند جواب صحیح داشت؟

Edge Caseها

یکی از رشته‌ها خالی باشد

هیچ کاراکتر مشترکی وجود نداشته باشد

دو رشته کاملاً برابر باشند

تفاوت حروف بزرگ و کوچک

یک سؤال رایج مصاحبه

اشتباه رایج: استفاده از منطق LCS

آیا الگوریتم سریع‌تری وجود دارد؟

جمع‌بندی

الگوریتم Kosaraju چیست و اصلاً چه مشکلی را حل می‌کند؟

Palindrome چیست؟ آموزش تشخیص رشته‌های قرینه با Two Pointers و TypeScript