بزرگترین زیررشته مشترک کیست؟ توضیح بده.
در علوم رایانه، "طولانی‌ترین زیررشته مشترک" (Longest Common Substring) به طولانی‌ترین رشته‌ای گفته می‌شود که به‌صورت متوالی در دو یا چند رشته دیگر ظاهر می‌شود. برای مثال، در رشته‌های "ABABC" و "BABCA"، زیررشته "ABC" طولانی‌ترین زیررشته مشترک است. این مفهوم در کاربردهایی مانند تشخیص سرقت ادبی و حذف داده‌های تکراری مفید است. این مسئله نباید با مسئله بلندترین زیردنباله مشترک اشتباه گرفته شود.(برای توضیحی در مورد تفاوت میان یک زیررشته و یک زیردنباله به زیررشته درمقابل زیردنباله رجوع کنید).مثال.طولانی‌ترین زیررشته مشترک از رشته‌های "ABAB", "BABA و "ABBA" ، رشته‌های "AB" و "BA" از طول دو هستند.دیگر زیر رشته‌های مشترک "A" و "B" هستند. ABAB BABA ABBAتعریف مسئله.با دو رشته داده شده،formula_1 از طولformula_2 و formula_3 از طول formula_4،بلندترین رشته‌هایی که زیر رشته‌های هر دوی formula_1 و formula_3 هستند را پیدا کنید.یک تعمیم از این مسئله، مسئله formula_7 زیررشته مشترک است.بارشته‌های داده شده formula_8 جایی که formula_9 و Σformula_10.الگوریتم‌ها.ما می‌توانیم طول‌ها و مکان‌های شروع بلندترین زیررشته‌های مشترک formula_1 و formula_3 را در زمان formula_13 به کمک درخت پسوندی توسعه یافته بیابیم.پیداکردن آن‌ها به کمک برنامه نویسی پویاهزینه‌ای معادل formula_14 دارد.راه حل مسئله تعمیم یافته،زمان formula_15 و formula_16 را می‌گیرد.درخت پسوندی.بزرگترین زیررشته مشترک از یک مجموعه از رشته‌ها می‌تواند توسط ساختن یک درخت پسوندی تعمیم یافته برای رشته‌ها ، و سپس یافتن عمیق‌ترین نودهای داخلی که گره‌های برگی که از همه رشته‌ها در درخت پایین اشان دارند ،یافت شود.شکل سمت چپ درخت پسوندی برای رشته‌های "ABAB" ،"BABA" و"ABBA" است که توسط پایانه‌های یکتای رشته‌ها خالی شده‌اند، تا "ABAB$0", "BABA$1" و "ABBA$2" شوند.گره‌هایی که "A", "B", "AB" و "BA" را نمایش می‌دهند همگی برگ‌های فرزندی از همهٔ رشته‌ها دارند،که با0،1 و 2 شماره‌گذاری شده‌اند.ساختن درخت پسوندی زمان formula_17 time می‌گیرد(طول الفبا ثابت است).اگردرخت از پایین به بالا با یک بردار بیتی که می‌گوید چه رشته‌هایی پایین هر گره دیده شده‌اند،پیمایش شود،مسئله K زیررشته مشترک می‌تواند در زمان formula_18 حل شود.اگردرخت پسوندی برای زمان ثابت بازیابی کم‌ترین پدران مشترک آماده شود،می‌تواند در زمان formula_19 time. حل شود.برنامه‌نویسی پویا.درابتدا بزرگترین پسوند مشترک رابرای همهٔ جفت پیشوندهای رشته بیابید.بزرگترین پسوند مشترکformula_20است.برای مثال رشته‌های "ABAB" و "BABA":حداکثراین طولانی‌ترین پسوندهای مشترک ازپیشوندهای مشترک باید طولانی‌ترین زیررشته‌های مشترک از S و T باشند.این‌ها در جدول،باقرمز،روی قطرها نمایش داده شده‌اند.برای این مثال طولانی‌ترین زیر رشته‌های مشترک "BAB" و "ABA" هستنداین مورد می‌تواند به بیش از دو رشته با اضافه کردن ابعاد بیشتر به جدول بسط داده شود.شبه کد.شبه کد پایین مجموعه بزرگترین زیر رشته‌های مشترک رامیان دورشته با برنامه نویسی پویا می‌یابد.function LCSubstr(S[1..m], T[1..n]) L := array(1..m, 1..n) z := 0 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]&gt; z z := L[i,j] if L[i,j] = z else L[i,j]=0; return retاین الگوریتم در زمان formula_22 اجرا می‌شود. متغیر codice_1 برای نگهداری طول بزرگترین زیررشته مشرک که ناکنون یافت شده‌است به کار می‌رود.مجموعه codice_2 برای نگهداری مجموعه‌ای از رشته‌ها که از طول codice_1 هستند به کار می‌رود.مجموعه codice_2 می‌تواند به‌طور کارایی توسط انباره کردن اندیس codice_5 ذخیره شود،که آخرین کاراکتر از طولانی‌ترین زیررشته مشترک(از اندازه Z) به جای codice_6 است.بنابراین همهٔ طولانی‌ترین زیررشته‌های مشترک به ازای هر i در codice_2, codice_8 خواهند بود.ترفندهای زیر می‌تواند برای کاهش حافظه در یک اجرا به کار رود.