برنامه یافتن بلندترین زیر رشته جناس قلب – به زبان ساده

در این مطلب، روش پیدا کردن بلندترین زیر رشته جناس قلب (Longest Palindromic Subsequence) بیان و پیاده‌سازی روش ارائه شده، با استفاده از زبان‌های برنامه‌نویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «سی» (C)، «جاوا» (Java)، «پایتون ۳» (Python 3) و «پی‌اچ‌پی» (PHP) انجام شده است. در اینجا، یک دنباله داده شده است. هدف، پیدا کردن طول بلندترین زیر رشته جناس قلب برای آن است.

به عنوان مثالی دیگر، اگر دنباله داده شده «BBABCBCAB» است، خروجی باید ۷ باشد، زیرا «BABCBAB» بلندترین زیر رشته دارای جناس قلب در این متن است. «BBBBB» و «BBCBB» نیز زیر رشته‌های دارای جناس قلب از دنباله داده شده به عنوان ورودی، هستند؛ اما بلندترین آن‌ها محسوب نمی‌شوند. راهکار ساده برای این مساله، تولید همه زیر دنباله‌ها از یک دنباله داده شده و پیدا کردن بلندترین زیر رشته جناس قلب است. این راهکار دارای پیچیدگی زمانی نمایی است.

ویژگی‌های برنامه‌نویسی پویا در مساله محاسبه بلندترین زیر رشته جناس قلب

در ادامه، بررسی می‌شود که این مساله چگونه هم دارای خصوصیات مهم «برنامه‌نویسی پویا» (Dynamic Programming | DP) است و هم می‌تواند به طور موثری با برنامه‌نویسی پویا حل شود.

• ساختار بهینه

فرض می‌شود X[0..n-1]‎ دنباله ورودی به طول n و L(0, n-1)‎ طول بلندترین زیر دنباله دارای جناس قلب X[0..n-1]‎ است. اگر اولین و آخرین کاراکترهای X مشابه باشند، داریم: L(0, n-1) = L(1, n-2) + 2؛ در غیر این صورت، L(0, n-1) = MAX (L(1, n-1), L(0, n-2))‎. در ادامه، یک راهکار بازگشتی متداول برای حل این مساله، ارائه شده است.

// Every single character is a palindrome of length 1
L(i, i) = 1 for all indexes i in given sequence

// IF first and last characters are not same
If (X[i] != X[j])  L(i, j) =  max{L(i + 1, j),L(i, j - 1)} 

// If there are only 2 characters and both are same
Else if (j == i + 1) L(i, j) = 2  

// If there are more than two characters, and first and last 
// characters are same
Else L(i, j) =  L(i + 1, j - 1) + 2

در ادامه، الگوریتم بالا به صورت خط به خط تشریح شده است.

// Every single character is a palindrome of length 1
L(i, i) = 1 for all indexes i in given sequence

هر کاراکتر یکتا، جناس قلبی به طول یک است. برای همه اندیس‌های i در یک دنباله داده شده، L(i, i) = 1 است.

// IF first and last characters are not same
If (X[i] != X[j]) L(i, j) = max{L(i + 1, j),L(i, j - 1)}

اگر اولین و آخرین کاراکتر مشابه نباشند، رابطه بالا برقرار است.

// If there are only 2 characters and both are same
Else if (j == i + 1) L(i, j) = 2

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

// If there are more than two characters, and first and last 
// characters are same
Else L(i, j) = L(i + 1, j - 1) + 2

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

• زیرمسائل هم‌پوشان

روش بازگشتی یافتن بلندترین زیر رشته جناس قلب

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

فیلم آموزش حل روابط بازگشتی + مفاهیم کلیدی در فرادرس

کلیک کنید

برنامه یافتن بلندترین زیر رشته جناس قلب در ++C به روش بازگشتی

برنامه پیدا کردن بلندترین زیر رشته جناس قلب در C به روش بازگشتی

برنامه پیدا کردن بلندترین زیر رشته جناس قلب در جاوا به روش بازگشتی

برنامه پیدا کردن بلندترین زیر رشته جناس قلب در پایتون ۳ به روش بازگشتی

برنامه پیدا کردن بلندترین زیر رشته جناس قلب در سی شارپ به روش بازگشتی

برنامه پیدا کردن بلندترین زیر رشته جناس قلب در PHP به روش بازگشتی

خروجی قطعه کدهای بالا به صورت زیر است.

The length of the LPS is 5

با در نظر داشتن پیاده‌سازی بالا، در ادامه «درخت بازگشتی جزئی» (Partial Recursion Tree) به طول ۶ با همه کاراکترهای متفاوت آن ارائه شده است.

L(0, 5)
             /        \ 
            /          \  
        L(1,5)          L(0,4)
       /    \            /    \
      /      \          /      \
  L(2,5)    L(1,4)  L(1,4)  L(0,3)

پیدا کردن بلندترین زیر رشته جناس قلب با برنامه‌نویسی پویا

در درخت بازگشتی جزئی که در بخش پیشین ارائه شد، L(1, 4)‎ دو بار حل می‌شود. اگر یک درخت بازگشتی کامل ترسیم شود، می‌توان مشاهده کرد که زیرمسائل بسیاری وجود دارند که دوباره و دوباره حل می‌شوند. از آنجا که مسائل مشابه چند بار فراخوانی می‌شوند، این مساله دارای خصوصیت زیرمسائل هم‌پوشان است.

بنابراین، مساله LPS هر دو خصوصیت مسائل برنامه‌نویسی پویا را دارد. مانند دیگر مسائل مرسوم برنامه‌نویسی پویا، محاسبه مجدد زیر مسائل مشابه با ساخت یک آرایه موقتی L[][]‎ به صورت پایین به بالا قابل انجام است.

برنامه پیدا کردن بلندترین زیر رشته جناس قلب در ++C به روش برنامه‌نویسی پویا

برنامه پیدا کردن بلندترین زیر رشته جناس قلب در جاوا به روش برنامه‌نویسی پویا

برنامه پیدا کردن بلندترین زیر رشته جناس قلب در پایتون به روش برنامه‌نویسی پویا

برنامه پیدا کردن بلندترین زیر رشته جناس قلب در #C به روش برنامه‌نویسی پویا

برنامه پیدا کردن بلندترین زیر رشته جناس قلب در PHP به روش برنامه‌نویسی پویا

خروجی قطعه کدهای بالا به صورت زیر است.

The lnegth of the LPS is 7

پیچیدگی زمانی پیاده‌سازی بالا از درجه O(n2)‎ است. این میزان، از پیچیدگی زمانی بدترین حالت پیاده‌سازی بازگشتی ساده نیز بهتر است.

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

• مجموعه آموزش‌های برنامه‌نویسی پایتون
• آموزش تکمیلی برنامه‌نویسی پایتون
• مجموعه آموزش‌های داده‌کاوی و یادگیری ماشین
• زبان برنامه‌نویسی پایتون (Python) — از صفر تا صد
• یادگیری علم داده (Data Science) با پایتون — از صفر تا صد
• آموزش پایتون (Python) — مجموعه مقالات جامع وبلاگ فرادرس

^^