نمایش مبدأ برای بزرگترین زیررشته مشترک

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

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

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

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

 ABAB
  |||
  BABA
   ||
 ABBA

== تعریف مسئله ==

با دو رشته داده شده،<math>S</math>  از طول<math>m</math> و <math>T</math>  از طول <math>n</math>،بلندترین رشته‌هایی که زیر رشته‌های هر دوی <math>S</math>  و <math>T</math>  هستند را پیدا کنید.یک تعمیم از این مسئله، مسئله <math>K</math> زیررشته مشترک است.بارشته‌های داده شده <math>S = \{S_1, ..., S_K\}</math> جایی که <math>|S_i|=n_i</math> و  &Sigma;<math>n_i = N</math>.

== الگوریتم‌ها ==

ما می‌توانیم طول‌ها و مکان‌های شروع بلندترین زیررشته‌های مشترک <math>S</math> و <math>T</math> را در زمان <math>\Theta(n+m)</math> به کمک [[درخت پسوندی توسعه یافته]] بیابیم.پیداکردن آن‌ها به کمک  [[برنامه نویسی پویا|برنامه نویسی پویاهزینه‌ای]] معادل <math>\Theta(nm)</math> دارد.راه [[حل مسئله]] تعمیم یافته،زمان <math>\Theta(n_1+...n_k)</math>  و <math>\Theta(n_1...n_k)</math>  را می‌گیرد.
== درخت پسوندی ==

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

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

ساختن درخت پسوندی زمان <math>\Theta(n)</math> time می‌گیرد(طول الفبا ثابت است).اگردرخت از پایین به بالا با یک بردار بیتی که می‌گوید چه رشته‌هایی پایین هر گره دیده شده‌اند،پیمایش شود،مسئله K زیررشته مشترک می‌تواند در زمان <math>\Theta(NK)</math> حل شود.اگردرخت پسوندی برای زمان ثابت بازیابی [[کم‌ترین پدران مشترک]] آماده شود،می‌تواند در زمان <math>\Theta(N)</math> time.<ref name="Gus97">{{cite book | last = Gusfield | first = Dan | origyear = 1997 | year = 1999 | title = Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology | publisher = Cambridge University Press | location = USA | isbn = 0-521-58519-8}}</ref> حل شود.
== برنامه‌نویسی پویا ==

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

برای مثال رشته‌های "ABAB" و "BABA":
{| class="wikitable" style="text-align:center"
|-
! width="15" | !! width="15" | !! width="15" |A !! width="15" |B !! width="15" |A !! width="15" |B
|-
| || 0 || 0 || 0 || 0 || 0
|-
! B
| 0 || 0 || style="color:red" |1 || 0 || 1
|-
! A
| 0 || style="color:red" |1 || 0 || style="color:red" |2 || 0
|-
! B
| 0 || 0 || style="color:red" |2 || 0 || style="color:red" |3
|-
! A
| 0 || 1 || 0 || style="color:red" | 3 || 0
|}

حداکثراین طولانی‌ترین پسوندهای مشترک ازپیشوندهای مشترک باید طولانی‌ترین زیررشته‌های مشترک از S و T باشند.این‌ها در جدول،باقرمز،روی قطرها نمایش داده شده‌اند.برای این مثال طولانی‌ترین زیر رشته‌های مشترک "BAB" و "ABA" هستند
.
:<math>
\mathit{LCSubstr}(S, T) = \max_{1 \leq i \leq m, 1 \leq j \leq n} \mathit{LCSuff}(S_{1..i}, T_{1..j}) \;
</math>
این مورد می‌تواند به بیش از دو رشته با اضافه کردن ابعاد بیشتر به جدول بسط داده شود.

== شبه کد ==

[[شبه کد]] پایین مجموعه بزرگترین زیر رشته‌های مشترک رامیان دورشته با [[برنامه نویسی پویا]] می‌یابد.<syntaxhighlight lang="cpp" start="0">
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
</syntaxhighlight>این الگوریتم در زمان <math>O(n m)</math> اجرا می‌شود. متغیر <code>z</code> برای نگهداری طول بزرگترین زیررشته مشرک که ناکنون یافت شده‌است به کار می‌رود.مجموعه <code>ret</code> برای نگهداری مجموعه‌ای از رشته‌ها که از طول <code>z</code> هستند به کار می‌رود.مجموعه  <code>ret</code> می‌تواند به‌طور کارایی توسط انباره کردن اندیس <code>i</code> ذخیره شود،که آخرین کاراکتر از طولانی‌ترین زیررشته مشترک(از اندازه Z) به جای <code>S[i-z+1..z]</code> است.بنابراین همهٔ طولانی‌ترین زیررشته‌های مشترک به ازای هر i در <code>ret</code>, <code>S[(ret[i]-z)..(ret[i])]</code> خواهند بود.

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

== جستارهای وابسته ==
*[[طولانی‌ترین زیررشته‌های پالیندروم]]

== متابع ==
{{پانویس}}

== پیوند به بیرون ==
*[//en.wikipedia.org/w/index.php?title=Longest_common_substring_problem]
*[http://search.cpan.org/perldoc?String::LCSS_XS Perl/XS implementation of the dynamic programming algorithm]
*[http://search.cpan.org/perldoc?Tree::Suffix Perl/XS implementation of the suffix tree algorithm]
*[[:b:en:Algorithm implementation/Strings/Longest common substring|Dynamic programming implementations in various languages on wikibooks]]
*[http://www.emanueleferonato.com/2010/12/01/solving-the-longest-common-substring-problem-with-as3/ working AS3 implementation of the dynamic programming algorithm]

[[رده:برنامه‌نویسی پویا]]
[[رده:ساختمان داده]]
[[رده:ساختمان داده و الگوریتم]]