v\:* {behavior:url(#default#VML);} o\:* {behavior:url(#default#VML);} w\:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);}
دو رشته زیر را در نظر بگیرید: هدف مقایسه این دو رشته و پیدا کردن شباهت بین آنها است. بزرگترین زیردنباله مشترک این طور تعریف می‌شود که دنباله‌ای مانند S3 است به طوری که حروف موجود در S3 با حفظ ترتیب در S1 و S2 موجود باشد. اما مطلقاً لزومی ندارد که متوالی باشد. از طرفی S3 باید بزرگترین دنباله ممکن با خواص بالا باشد. به طور کلی اگر دو رشته و را در نظر بگیریم٫ یک بلندترین زیر دنباله مشترک را می‌توان با استفاده از برنامه نویسی پویا   پیدا کرد v\:* {behavior:url(#default#VML);} o\:* {behavior:url(#default#VML);} w\:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);} Normal 0 false false false false EN-US X-NONE FA /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-qformat:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin-top:0cm; mso-para-margin-right:0cm; mso-para-margin-bottom:10.0pt; mso-para-margin-left:0cm; line-height:115%; mso-pagination:widow-orphan; font-size:11.0pt; font-family:"Calibri","sans-serif"; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin;} مساله LCS دارای خصوصیت بهینه سازی   (Optimal Substructure) است: مساله LCS را می‌توان به زیر مساله‌های کوچکتر تقسیم نمود. که این زیر مساله‌ها جفت دنباله‌های پیشوندی دو دنباله ورودی هستند. اگر داشته باشیم: ٫ آن گاه Xi به این صورت تعریف می‌شود: فرض کنید و دو رشته باشند و بلندترین زیردنباله مشترک یا LCS دو رشته Y و X باشند. پیاده سازی الگوریتم با استفاده از روش برنامه نویسی پویا به این صورت است: ۱)اگر باشد٫ آن گاه Zk = Xm = Yn و Zk − 1 یک LCS برای Yk − 1 و Xk − 1 است. ۲)اگر باشد٫ آن گاه نتیجه می‌دهد که Z یک LCS برای Y و Xm − 1 است. ۳)اگر باشد٫ آن گاه نتیجه می‌دهد که Z یک LCS برای Yn − 1 و X است. قضیه فوق نشان می‌دهد: LCS دو رشته٫ در داخل خودش٫ حاوی یک LCS برای پیشوندهای آن دو رشته نیز می‌باشد.    v\:* {behavior:url(#default#VML);} o\:* {behavior:url(#default#VML);} w\:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);} Normal 0 false false false false EN-US X-NONE FA /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-qformat:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin-top:0cm; mso-para-margin-right:0cm; mso-para-margin-bottom:10.0pt; mso-para-margin-left:0cm; line-height:115%; mso-pagination:widow-orphan; font-size:11.0pt; font-family:"Calibri","sans-serif"; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin;} فرض کنید یک عنصر از آرایه C باشد که نشان دهنده طول LCS دو دنبالهXi و Yi است. بنابراین اگر i=0 یا j=0 باشد٫ یکی از دنباله‌ها دارای طول صفر است و در نتیجه LCS دو دنباله صفر خواهد شد. 0\ and\ X_{m}= Y_{n} \\ max(c[i-1,j],c[i,j-1]) & i,j>0\ and\ X_{i}\ne Y_{j} \end{cases} " src="file:///C:/DOCUME~1/hamid/LOCALS~1/Temp/msohtmlclip1/01/clip_image002.gif" />بنابراین وقتی که باشد٫ زیر مساله ما پیدا کردن LCS برای Xi − 1 و Yi − 1 است. در غیر این صورت ما دو زیر مساله داریم: پیدا کردن LCS برای Yi و Xi − 1 و پیدا کردن LCS برای Yi − 1 و Xi االگوریتم را با استفاده از روش برنامه نویسی پویا پیاده سازی می‌کنیم. الگوریتم دو رشته و را به عنوان ورودی دریافت می‌کند(شکل ۲). الگوریتم مقادیر که نشان دهدنده طول LCS است را داخل آرایه ذخیره می‌کند. عناصر آرایه به ترتیب row-major پر می‌شوند. یهنی ابتدا اولین سطر c به ترتیب از چپ به راست پر می‌شود، سپس سطر دوم و الی آخر. علاوه بر این الگوریتم آرایه دیگری به نام را نیز پر می‌کند. این آرایه جهت حرکت را ذخیره می‌کند. شکل ۲ مقدار b با علامت‌های جهت پر می‌شود. همین طور مقدار به این بستگی دارد که آیا xi = yi باشد (خط ۹). جهت فلش‌ها طوری انتخاب می‌شود که همواره حرکت به سمت خانه‌ای با طول LCS بزرکتر را تضمین می‌کند. در نهایت برای پیدا کردن LCS از گوشه سمت راست و پایین آرایه b در جهت پیکان‌ها به سمت گوشه بالا و چپ آرایه حرکت می‌کنیم v\:* {behavior:url(#default#VML);} o\:* {behavior:url(#default#VML);} w\:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);} Normal 0 false false false false EN-US X-NONE FA /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-qformat:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin-top:0cm; mso-para-margin-right:0cm; mso-para-margin-bottom:10.0pt; mso-para-margin-left:0cm; line-height:115%; mso-pagination:widow-orphan; font-size:11.0pt; font-family:"Calibri","sans-serif"; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin;} زمانی که تعداد دنباله‌های ورودی ثابت باشند٫ این مساله توسط برنامه نویسی پویا در زمان چندجمله ایحل می‌شود. فرض کنید N دنباله ورودی به طول n1,n2,...,nN داشته باشیم. یک راه حل ابتدایی برای جستجوی LCS این است که هر یک از زیردنباله دنباله اولی را برررسی کنیم که آیا زیر دنباله برای دیگر دنباله‌های ورودی است یا خیر. هر زیر ددنباله درزمانی خطی متناسب با طول دنباله‌های باقی مانده بررسی می‌شود. بنابراین زمان الگوریتم برابر خواهد بود با:1} n_i\right)." src="file:///C:/DOCUME~1/hamid/LOCALS~1/Temp/msohtmlclip1/01/clip_image002.gif" /> برای حالت ورودی با دو دنباله با n و m عنصر٫ پیچیدگی زمانیالگوریتم برابر خواهد بود. برای تعداد ورودی‌های دلخواه برنامه نویسی پویا راه حلی با این زمان ارایه می‌کند: توابعی با پیچیدگی کمتر موجود است.   function print_LCS (b,X,i,j)   if i=0 or j=0 then      return   if b[i,j] = '' then      print_LCS(b,X,i-1,j-1)      print xi   else if b[i,j]= '' then      print_LCS(b,X,i,j-1)   else print_LCS(b,X,i,j-1)