بزرگترین زیردنباله مشترک
يكشنبه, ۱۶ بهمن ۱۳۹۰، ۱۱:۳۲ ق.ظ
Longest common subsequence
شرح مساله(ویکی پدیا) :
دو رشته زیر را در نظر بگیرید:
هدف مقایسه این دو رشته و پیدا کردن شباهت بین آنها است. بزرگترین زیردنباله مشترک این طور تعریف می‌شود که دنباله‌ای مانند 
است به طوری که حروف موجود در با حفظ ترتیب در 
و 
موجود باشد. اما مطلقاً لزومی ندارد که متوالی باشد. از طرفی باید بزرگترین دنباله ممکن با خواص بالا باشد. به طور کلی اگر دو رشته 
و 
را در نظر بگیریم٫ یک بلندترین زیر دنباله مشترک را میتوان با استفاده از برنامه نویسی پویا پیدا کرد.
شرح الگوریتم: الگوریتم LCS الگوریتمی برای یافتن بزرگترین زیر دنباله مشترک بین دو دنباله است که با بهره گیری از برنامه ریزی پویا اجرا می شود . این الگوریتم از O ی m*n است ....
فرض کنید دو رشته به صورت a و b با طول های n و m داریم و ai یعنی کاراکتر i ام رشته a .
آرایه LCS را به این صورت تعریف می کنیم که هر خانه i,j از ارایه نشان گر اندازه بزرگتین زیر دنباله مشترکی باشد که میتوان تنها با استفاده از i کاراکتر اول رشته a و j کاراکتر اول رشته b ساخت .
هر خانه i,j را می توان با توجه با خانه های کوچکتر به دست آور به صورتی که
اگر ai=bj طول بزرگترین زیر دنباله مشترک i,j برابر با طول بزرگترین زیر دنباله مشترک i-1,j-1 به اضافه ی 1 است .
و اگر ai != bi طول بزرگترین زیر دنباله مشترک آنها برابر با ماکسیمم طول بزرگترین زیر دنباله i-1,j و i,j-1 است .
در نهایت مقدار خروجی برابر با مقدار درایه n,m از آرایه LCS است .
کد الگوریتم ( سی پلاس پلاس ) : http://snipt.net/JahanaraCo/lcs-1
:)