المپدیا

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

ابزار کاربر

ابزار سایت


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

Wildcards

یک «الگو» رشته‌ای است که از حروف کوچک الفبای انگلیسی و حرف * تشکیل شده است. الگوی $s$ با رشته‌ی $t$، شامل حروف کوچک الفبای انگلیسی، «مطابقت» دارد اگر بتوان هر یک از حروف * درون $s$ را با رشته‌ی دیگری(شامل رشته‌ی تهی) جایگزین کرد تا رشته‌ی $t$ به دست آید. توجه کنید که می‌توان دو حرف * متفاوت در $s$ را با رشته‌های متفاوتی جایگزین کرد. سندباد دو رشته‌ی $A$ و $B$ را پیدا کرده است که از حروف کوچک الفبای انگلیسی، تشکیل شده‌اند. کوچک‌ترین الگویی را پیدا کنید که با رشته‌ی $A$ مطابقت کند ولی با رشته‌ی $B$ مطابقت نکند. اگر چندین الگو با این خاصیت وجود داشت، الگویی را پیدا کنید که کم‌ترین تعداد حرف * را دارد.

لازم به ذکر است که طول یک رشته مانند $h$ را با $|h|$ نشان می‌دهیم.

ورودی

در خط اول ورودی، رشته‌ی $A$ آمده است. در خط دوم ورودی، رشته‌ی $B$ آمده است.

خروجی

در تنها خط خروجی، الگوی خواسته شده را چاپ کنید. در صورتی که چندین الگو با کم‌ترین طول و کم‌ترین تعداد * وجود داشت، یکی را به دلخواه چاپ کنید.

زیرمسئله‌ها

  • زیرمسئله اول (۲۰ نمره): $|A|, |B| \le 10$
  • زیرمسئله دوم (۸۰ نمره): بدون محدودیت اضافی

محدودیت‌ها

  • $1 \le |A|, |B| \le 50$, $A \neq B$

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

ورودی نمونه خروجی نمونه
a
b
a
abaa
aaaa
ab*
aaabaaaabaaa
aaabaaabaaa
*aaaa*

شرح ورودی و خروجی نمونه

در نمونه‌ی ورودی سوم،‌ چون در رشته‌ی $B$، چهار حرف $a$ به طور متوالی نیامده‌اند، الگوی *aaaa* با این رشته مطابقت نمی‌کند. از طرفی اگر به جای اولین حرف *، رشته‌ی aaabو به جای دومین حرف *، رشته‌ی baaa را جایگزین کنیم،‌ رشته‌ی $A$ به دست می‌آید. در نتیجه این الگو در رشته‌ی $A$ صدق می‌کند اما در رشته‌ی $B$ صدق نمی‌کند. از طرفی می‌توان اثبات کرد این رشته کوتاه‌ترین الگویی است که این خاصیت را دارد و در بین تمام کوتاه‌ترین الگوهای با این خاصیت، بیشترین تعداد ستاره را دارد.


ابزار صفحه