- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
بریم ببینیم برنامه چیه!
در کمال ناباوری محمد این جمله معروفش را هم گفت و به همه ثابت کرد روش عجیبی که برای نزدیک کردن فاصله ذهنشان پیش گرفتند جواب داد! اکنون فاصله بین ذهن محمد و عرفان به سمت صفر میل میکند و آنها مقدار زیادی خوشحالاند! قبل از اینکه بالاخره شروع به توسعه دادن پروژه کنند تصمیم گرفتند که اندکی برای دستگرمی با هم کد بزنند ولی متاسفانه هنوز به کدزدن با زبان ++C تسلط کافی ندارند.
از آنجایی که محمد و عرفان هیچ کدام از کارهایشان عادی نبوده، یادگیری ++Cشان هم از این قاعده مستثنی نیست! آنها از شما درخواست کردند که با حل یک سوال کمک کنید تا به طور کامل به ++C مسلط شوند!
رشته \(S\) برای رشته \(T\) یک وارواژه است اگر بتوان با جابهجا کردن حروف رشته \(S\) به رشته \(T\) رسید. برای مثال aba وارواژه رشته aab است اما وارواژه رشته aaa نیست.
رشته \(S\) رشتهای است که شامل حروف کوچک زبان انگلیسی و تعدادی کاراکتر \(?\) است. همچنان رشته \(P\) رشتهای است که تنها شامل حروف کوچک انگلیسی است. زیررشتهای از \(S\) را زیررشته خوب میگوییم اگر بتوان با قرار دادن حروف دلخواه بجای \(?\)، به وارواژهای از \(P\) دست یافت.
ورودی
در این سوال به شما ابتدا رشته \(S\) و بعد \(p\) داده میشود.
\[1 \le |S|, |p| \le 1\ 000\]
خروجی
خروجی تنها شامل یک خط است که در آن یک عدد صحیح برابر تعداد زیر رشتههای خوب رشته \(S\) چاپ شود.
مثال
ورودی نمونه ۱
bb??x???
aab
خروجی نمونه ۱
2
در این نمونه دو زیررشته b?? و ???میتوانند با جایگزین شدن علامت سوالهایشان و تبدیل شدن به baa و aab وارواژه رشته \(P\) شوند.
ورودی نمونه ۲
ab?c
acb
خروجی نمونه ۲
2
در این مثال دو زیررشته ab? و b?c با تبدیل شدن به abc و bac می توانند وارواژه رشته acb شوند.