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

در علوم کامپیوتر ، مسئله طولانی ترین زیررشته مشترک یافتن طولانی ترین رشته (یا رشته هایی) است که زیررشته (یا زیر رشته هایی) از دو یا چند رشته است.

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

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

مثال

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

ABAB
 |||
 BABA
  ||
ABBA

تعریف مسئله

با دو رشته داده شده، $S$

از طول

m

و

T

از طول

n

،بلندترین رشته‌هایی که زیر رشته‌های هر دوی

S

و

T

هستند را پیدا کنید.یک تعمیم از این مسئله، مسئله

K

زیررشته مشترک است.بارشته‌های داده شده

S=\{S_{1},...,S_{K}\}

جایی که

|S_{i}|=n_{i}

و Σ

n_{i}=N

.

الگوریتم‌ها

ما می‌توانیم طول‌ها و مکان‌های شروع بلندترین زیررشته‌های مشترک $S$

و

T

را در زمان

\Theta (n+m)

به کمک درخت پسوندی توسعه یافته بیابیم.پیداکردن آن‌ها به کمک برنامه نویسی پویاهزینه‌ای معادل

\Theta (nm)

دارد.راه حل مسئله تعمیم یافته،زمان

\Theta (n_{1}+...n_{k})

و

\Theta (n_{1}...n_{k})

را می‌گیرد.

درخت پسوندی

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

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

ساختن درخت پسوندی زمان $\Theta (n)$

time می‌گیرد(طول الفبا ثابت است).اگردرخت از پایین به بالا با یک بردار بیتی که می‌گوید چه رشته‌هایی پایین هر گره دیده شده‌اند،پیمایش شود،مسئله K زیررشته مشترک می‌تواند در زمان

\Theta (NK)

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

\Theta (N)

time. حل شود.

برنامه‌نویسی پویا

درابتدا بزرگترین پسوند مشترک رابرای همهٔ جفت پیشوندهای رشته بیابید.بزرگترین پسوند مشترک ${\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":

	A	B	A	B
	0	0	0	0
B	0	1	0	1
A	1	0	2	0
B	0	2	0	3
A	1	0	3	0

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

{\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

این الگوریتم در زمان $O(nm)$

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

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

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

جستارهای وابسته

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

متابع

↑ Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8.

پیوند به بیرون

[Gus97-1] Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8.