رشته‌ی ‎$S=c_1 c_2 \dots c_n$‎ به طول ‎$n$‎ حرف را در نظر بگیرید. حروف این رشته از مجموعه‌ای دلخواه انتخاب شده‌اند. یک زیررشته از این رشته، تعدادی حرف آن است که بطور متوالی در رشته ظاهر شده‌اند. مساله بازسازی رشته به این صورت تعریف می‌شود:

همه‌ی ‎$n-k+1$‎ زیررشته‌ی ‎$k$‎ حرفی از ‎$S$‎ داده شده‌اند. توجه کنید که ممکن است بعضی از این زیررشته‌ها چند بار در رشته‌ی ‎$S$‎ ظاهر شده‌باشند، در این صورت تعداد دفعات تکرار هر یک را نیز می‌دانیم. می‌خواهیم رشته‌ی اولیه را بازسازی کنیم. به عبارت دیگر رشته‌ای به طول ‎$n$‎ بیابیم که زیر رشته‌های ‎$k$‎ حرفی‌اش دقیقاً منطبق بر زیررشته‌های داده شده (با همان تعداد دفعات تکرار) باشد. جواب مساله لزوماً یکتا نیست؛ ارائه‌ی یک بازسازی کافی است‎.‎

الگوریتمی از مرتبه‌ی چندجمله‌ای برای حل مساله بازسازی رشته ارائه کنید.

• سوال بعد
• سوال قبل