الفبای $A=\{a_1,a_2,...,a_k\}$ داده شده است. ورودی دو رشته‌ی $S_1$ و $S_2$ به طول‌های $n$ و $m$ از الفبای $A \cup \{*\}$ است. نویسه‌ی * می‌تواند هر رشته‌ از الفبای $A$ باشد. می‌خواهیم کوتاه‌ترین رشته‌ی $S$ از الفبای $A$ را طوری پیدا کنیم تا $S_1$ و $S_2$، پس از گسترش *، زیر رشته‌هایی از $S$ شوند. مثلا، اگر $A=\{a,c,g,t\}$، $S_1=*a*cgta*aa*g*$ و $S_2=*a*gtcg*ag*$، $S=agtcgtaaag$ یک جواب است. الگوریتمی کارا برای این مسئله ارئه دهید.

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