اوقات فراغت


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

محمدجواد که پشت‌کار بالایی دارد، در اوقات فراغت از کارش، جدول حل می‌کند. او این بار به جدولی برخورده که از حروف کوچک الفبای انگلیسی تشکیل شده است و در انتهای آن کلمه ای داده شده که باید تعداد تکرار های آن در جدول شمرده شود. هر تکرار کلمه در جدول به معنای ظاهر شدن کلمه مورد نظر به صورت افقی و از چپ به راست یا عمودی و از بالا به پایین در قسمتی از جدول است. برای مثال در جدول زیر، کلمه queraquera ۲ بار و کلمه snowsnow ۱ بار تکرار شده است. (برای درک بهتر صورت سوال به نمونه ها مراجعه کنید.)

quera
users
enjoy
round
award
Plain text

محمدجواد که باید به زودی به سر کارش برگردد، از شما خواسته جدول را برایش حل کنید.

ورودی🔗

در سطر اول ورودی اعداد nn و mm می‌آیند که نشان دهنده تعداد سطر ها و تعداد ستون های جدول هستند. در ادامه nn خط می‌آید که در iiمین آنها رشته ای به طول mm متشکل از حروف کوچک الفبای انگلیسی آمده که نشان دهنده iiمین سطر جدول است. در آخرین خط ورودی رشته ss می‌آید که نشان دهنده کلمه مورد جستجو در جدول است.

1n,m50 1 \le n, m \le 50 1s50 1 \le |s| \le 50

خروجی🔗

در تنها خط خروجی باید تعداد تکرار های کلمه مورد نظر در جدول چاپ شود.

مثال🔗

ورودی نمونه ۱🔗

5 5
quera
users
enjoy
round
award
quera
Plain text

خروجی نمونه ۱🔗

2
Plain text

ورودی نمونه ۲🔗

2 8
abababab
babababa
baba
Plain text

خروجی نمونه ۲🔗

5
Plain text

کلمه baba به صورت افقی و از چپ به راست در سطر اول ۲ بار و در سطر دوم ۳ بار ظاهر شده است و به صورت عمودی و از بالا به پایین در جدول ظاهر نشده است.