یک «الگو» رشتهای است که از حروف کوچک الفبای انگلیسی و حرف * تشکیل شده است. الگوی s با رشتهی t، شامل حروف کوچک الفبای انگلیسی، «مطابقت» دارد اگر بتوان هر یک از حروف * درون s را با رشتهی دیگری(شامل رشتهی تهی) جایگزین کرد تا رشتهی t به دست آید. توجه کنید که میتوان دو حرف * متفاوت در s را با رشتههای متفاوتی جایگزین کرد. سندباد دو رشتهی A و B را پیدا کرده است که از حروف کوچک الفبای انگلیسی، تشکیل شدهاند. کوچکترین الگویی را پیدا کنید که با رشتهی A مطابقت کند ولی با رشتهی B مطابقت نکند. اگر چندین الگو با این خاصیت وجود داشت، الگویی را پیدا کنید که کمترین تعداد حرف * را دارد.
لازم به ذکر است که طول یک رشته مانند h را با |h| نشان میدهیم.
در خط اول ورودی، رشتهی A آمده است. در خط دوم ورودی، رشتهی B آمده است.
در تنها خط خروجی، الگوی خواسته شده را چاپ کنید. در صورتی که چندین الگو با کمترین طول و کمترین تعداد * وجود داشت، یکی را به دلخواه چاپ کنید.
ورودی نمونه | خروجی نمونه |
---|---|
a b | a |
abaa aaaa | ab* |
aaabaaaabaaa aaabaaabaaa | *aaaa* |
در نمونهی ورودی سوم، چون در رشتهی B، چهار حرف a به طور متوالی نیامدهاند، الگوی *aaaa* با این رشته مطابقت نمیکند. از طرفی اگر به جای اولین حرف *، رشتهی aaabو به جای دومین حرف *، رشتهی baaa را جایگزین کنیم، رشتهی A به دست میآید. در نتیجه این الگو در رشتهی A صدق میکند اما در رشتهی B صدق نمیکند. از طرفی میتوان اثبات کرد این رشته کوتاهترین الگویی است که این خاصیت را دارد و در بین تمام کوتاهترین الگوهای با این خاصیت، بیشترین تعداد ستاره را دارد.