با سلام و درود
اگه کسی در مورد این مسیله نظری داره ممنون میشم راهنمایی کنید:
Given an algorithm that take a long string as an input and find the longest palindrome subsequence in cubic time.
در واقع حل مسیله longest palindrome subsequence میشه که براش ۳ راه وجود داره:
۱. در نظر گرفتن همه ساب‌سیکوینس‌های موجود که زمان اجراش اکسپوننشال میشه
۲. معکوس‌کردن رشته ورودی و پیدا کردن طولانی‌ترین ساب‌سیکوینس مشترک بین رشته و معکوس رشته.
Longest_Common_Subsequence(OriginalStr, ReverseStr)
۳. از طریق داینامیک پروگرمینگ و پیدا کردن رابطه ریکرسیو همونطور که تو لینک توضیح داده شده.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
در حالت دوم و سوم زمان اجرا برابر [tex]O(n^2)[/tex]
در حالیکه در مسیله زمان اجرایی برابر با [tex]O(n^3)[/tex] خواسته شده.
کسی در این مورد نظری داره؟
