المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۳:سوال ۳

کوتاه‌ترین ابر رشته‌ی مشترک

رشته‌ی $S=s_1s_2…s_k$ دنباله‌ای به طول $k$ از نویسه‌های $a$ تا $z$ است. رشته‌ی $T=t_1t_2…t_m$ زیر رشته‌ای از $S=s_1s_2…s_k$ نامیده می‌شود، هرگاه $(0\leq i \leq m-1)i$ وجود داشته باشد به طوری که به ازای هر $1\leq j \leq m$ داشته باشیم $s_{i+j}=t_j$. در این صورت می‌گوییم $S$ ابر رشته‌ی $T$‌ است.

مسئله به این صورت است: $n$ رشته‌ی $T_1$، $T_2$،… و $T_n$ که طول هر یک از آن‌ها حداکثر ۲ است داده شده‌اند. می‌خواهیم رشته‌ی $S$ با کم‌ترین طول را پیدا کنیم که تمام $T_i$ ها زیر رشته‌ی آن باشند $(n \leq 100)$.

برنامه‌ای بنوسید که:

  1. رشته‌های $T_1$، $T_2$،… و $T_n$ را از فایل ورودی بخواند و این رشته‌ها را در فایل خروجی بنویسد. در هر سطر فایل ورودی یک رشته نوشته شده است. ورودی ممکن است شامل لیست‌های مختلفی باشد که موارد مختلف با یک سطر خالی از هم جدا شده‌اند.
  2. رشته‌ی $S$ را طوری به‌دست آورد که تمام رشته‌های $T_1$، $T_2$،… و $T_n$ زیر رشته‌ی آن باشند و طول آن کمینه باشد. این رشته را در فایل خروجی بنویسید.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
ab
bc
ca
dc
b
k
ad

ab
ac
ad
e
fa
ab
bc
ca
dc
b
k
ad
The Shortest Common Superstring = abcadck
ab
ac
ad
e
fa‎ The Shortest Common Superstring = fabacade

ابزار صفحه