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

المپدیا

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

ابزار کاربر

ابزار سایت


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

Wildcards

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

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

ورودی

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

خروجی

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

زیرمسئله‌ها

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

محدودیت‌ها

  • 1|A|,|B|50, AB

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

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

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

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


ابزار صفحه