Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۵:الگوریتم ها:سوال ۵

سوال ۵

دو رشته‌ی s و t با طول‌های n و m داریم. یک زیردنبالک را یک زیردنباله از یک دنباله گوییم؛ هرگاه بین هر دو حرف متوالی زیردنبالک، در دنباله‌ی اصلی حداقل k حرف دیگر وجود داشته باشد. طول بلند‌ترین زیردنبالک مشترک بین s,t را با الگوریتمی از O(nm) بیابید.


ابزار صفحه