بزرگترین زیررشته مشترک

در علوم رایانه، "طولانی‌ترین زیررشته مشترک" (Longest Common Substring) به طولانی‌ترین رشته‌ای گفته می‌شود که به‌صورت متوالی در دو یا چند رشته دیگر ظاهر می‌شود. برای مثال، در رشته‌های "ABABC" و "BABCA"، زیررشته "ABC" طولانی‌ترین زیررشته مشترک است. این مفهوم در کاربردهایی مانند تشخیص سرقت ادبی و حذف داده‌های تکراری مفید است.

این مسئله نباید با مسئله بلندترین زیردنباله مشترک اشتباه گرفته شود.(برای توضیحی در مورد تفاوت میان یک زیررشته و یک زیردنباله به زیررشته درمقابل زیردنباله رجوع کنید).

طولانی‌ترین زیررشته مشترک از رشته‌های "ABAB", "BABA و "ABBA" ، رشته‌های "AB" و "BA" از طول دو هستند.دیگر زیر رشته‌های مشترک "A" و "B" هستند.

ABAB
 |||
 BABA
  ||
ABBA

با دو رشته داده شده،${\displaystyle S}$ از طول${\displaystyle m}$ و ${\displaystyle T}$ از طول ${\displaystyle n}$،بلندترین رشته‌هایی که زیر رشته‌های هر دوی ${\displaystyle S}$ و ${\displaystyle T}$ هستند را پیدا کنید.یک تعمیم از این مسئله، مسئله ${\displaystyle K}$ زیررشته مشترک است.بارشته‌های داده شده ${\displaystyle S=\{S_{1},...,S_{K}\}}$ جایی که ${\displaystyle |S_{i}|=n_{i}}$ و Σ${\displaystyle n_{i}=N}$.

ما می‌توانیم طول‌ها و مکان‌های شروع بلندترین زیررشته‌های مشترک ${\displaystyle S}$ و ${\displaystyle T}$ را در زمان ${\displaystyle \Theta (n+m)}$ به کمک درخت پسوندی توسعه یافته بیابیم.پیداکردن آن‌ها به کمک برنامه نویسی پویاهزینه‌ای معادل ${\displaystyle \Theta (nm)}$ دارد.راه حل مسئله تعمیم یافته،زمان ${\displaystyle \Theta (n_{1}+...n_{k})}$ و ${\displaystyle \Theta (n_{1}...n_{k})}$ را می‌گیرد.

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

شکل سمت چپ درخت پسوندی برای رشته‌های "ABAB" ،"BABA" و"ABBA" است که توسط پایانه‌های یکتای رشته‌ها خالی شده‌اند، تا "ABAB$0", "BABA$1" و "ABBA$2" شوند.گره‌هایی که "A", "B", "AB" و "BA" را نمایش می‌دهند همگی برگ‌های فرزندی از همهٔ رشته‌ها دارند،که با0،1 و 2 شماره‌گذاری شده‌اند.

ساختن درخت پسوندی زمان ${\displaystyle \Theta (n)}$ time می‌گیرد(طول الفبا ثابت است).اگردرخت از پایین به بالا با یک بردار بیتی که می‌گوید چه رشته‌هایی پایین هر گره دیده شده‌اند،پیمایش شود،مسئله K زیررشته مشترک می‌تواند در زمان ${\displaystyle \Theta (NK)}$ حل شود.اگردرخت پسوندی برای زمان ثابت بازیابی کم‌ترین پدران مشترک آماده شود،می‌تواند در زمان ${\displaystyle \Theta (N)}$ time.^[۱] حل شود.

درابتدا بزرگترین پسوند مشترک رابرای همهٔ جفت پیشوندهای رشته بیابید.بزرگترین پسوند مشترک ${\displaystyle {\mathit {LCSuff}}(S_{1..p},T_{1..q})={\begin{cases}{\mathit {LCSuff}}(S_{1..p-1},T_{1..q-1})+1&\mathrm {if} \;S[p]=T[q]\\0&\mathrm {otherwise} .\end{cases}}}$ است.

برای مثال رشته‌های "ABAB" و "BABA":

حداکثراین طولانی‌ترین پسوندهای مشترک ازپیشوندهای مشترک باید طولانی‌ترین زیررشته‌های مشترک از S و T باشند.این‌ها در جدول،باقرمز،روی قطرها نمایش داده شده‌اند.برای این مثال طولانی‌ترین زیر رشته‌های مشترک "BAB" و "ABA" هستند .

${\displaystyle {\mathit {LCSubstr}}(S,T)=\max _{1\leq i\leq m,1\leq j\leq n}{\mathit {LCSuff}}(S_{1..i},T_{1..j})\;}$

این مورد می‌تواند به بیش از دو رشته با اضافه کردن ابعاد بیشتر به جدول بسط داده شود.

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

function LCSubstr(S[1..m], T[1..n])
 L := array(1..m, 1..n)
    z := 0
    ret := {}
    for i := 1..m
        for j := 1..n
            if S[i] = T[j]
                if i = 1 or j = 1
                    L[i,j] := 1
                else
                    L[i,j] := L[i-1,j-1] + 1
                if L[i,j]> z
                    z := L[i,j]
                    ret := {}
                if L[i,j] = z
                    ret := ret ∪ {S[i-z+1..i]}
            else L[i,j]=0;
    return ret

این الگوریتم در زمان ${\displaystyle O(nm)}$ اجرا می‌شود. متغیر z برای نگهداری طول بزرگترین زیررشته مشرک که ناکنون یافت شده‌است به کار می‌رود.مجموعه ret برای نگهداری مجموعه‌ای از رشته‌ها که از طول z هستند به کار می‌رود.مجموعه ret می‌تواند به‌طور کارایی توسط انباره کردن اندیس i ذخیره شود،که آخرین کاراکتر از طولانی‌ترین زیررشته مشترک(از اندازه Z) به جای S[i-z+1..z] است.بنابراین همهٔ طولانی‌ترین زیررشته‌های مشترک به ازای هر i در ret, S[(ret[i]-z)..(ret[i])] خواهند بود.

ترفندهای زیر می‌تواند برای کاهش حافظه در یک اجرا به کار رود.

• فقط آخرین و سطرکنونی جدول برنامه نویسی پویارابرای ذخیره حافظه (${\displaystyle O(\min(m,n))}$ به جای ${\displaystyle O(nm)}$ نگاه دارید.
• فقط مقادیر غیر صفر را در سطرها نگهداری کنید.این امر می‌تواند توسط استفاده از جداول هش به جای آرایه‌ها انجام شود.این امر برای الفباهای بزرگ مفید است.

• طولانی‌ترین زیررشته‌های پالیندروم

• Perl/XS implementation of the dynamic programming algorithm
• Perl/XS implementation of the suffix tree algorithm
• Dynamic programming implementations in various languages on wikibooks
• working AS3 implementation of the dynamic programming algorithm