اکبر در درخت کبیر


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

کاراکتر "من" که دید اکبر بدون اجازه از اسمش در سوال ها استفاده کرده است، تصمیم گرفت انتقام بگیرد.

در سرزمین "اکبراینا" درختی کبیر وجود داشت، درخت کبیر درختی ریشه‌دار بی نهایت راس است که هر راس آن دارای 26 فرزند است. امیرمحمد که به نام‌گذاری رئوس درخت علاقه زیادی دارد، به هر راسی از این درخت رشته‌ای از حروف کوچک انگلیسی را متناظر کرد، میدانیم نام‌گذاری امیرمحمد خاصیت های زیر را دارد:

  • به راس ریشه رشته تهی متناظر شده است.
  • به هیچ دو راسی رشته یکسان متناظر نشده است.
  • به ازای هر راسی به جز ریشه اگر رشته متناظر این راس .s1s2s3...sks_1 s_2 s_3...s_k باشد، رشته متناظر پدر این راس s1s2s3...sk1 s_1 s_2 s_3 ... s_{k-1} است.

بعد از نام‌گذاری امیرمحمد، امید به وجد آمد و رفت که از راس‌های این درخت بازدید کنه، ولی بعد از مدتی کوتاه فهمید که تو راسی به نام OO با یک رشته mm حرفی قرار داره و گم شده. برای همین به اکبر (مالک سرزمین و همچنین مالک درخت کبیر) زنگ زد و گفت: "اکبرر بیا منو پیدا کن گم شدم". اکبر که در آن لحظه در راسی به نام AA با nn حرف قرار داشت، امید خود را از دست نداد و به سمت امید دوید، او می‌توانست در هر ثانیه از یک راس به یکی از راس های مجاورش برود، و چون خیلی نگران از بین رفتن امیدش بود، در کوتاه ترین زمان ممکن امید خود را بدست آورد. حال شما به عنوان شنونده این داستان پندآموز به ما اعلام کنید که اکبر چند ثانیه پس از حرکت، امید خود را بدست می آورد.

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

ورودی🔗

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

1n,m100 0001 \le n, m \le 100\ 000

خروجی🔗

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

مثال🔗

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

2
ab
2
ac
Plain text

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

2
Plain text

اکبر در ثانیه اول از abab به aa میرود، و در ثانیه دوم از aa به acac میرود و امیدش با بدست می‌آورد.

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

3
aab
3
aba
Plain text

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

4
Plain text

اکبر در ثانیه اول از aabaab به aaaa می‌رود، در ثانیه دوم از aaaa به aa می‌رود، در ثانیه سوم از aa به abab می‌رود، در ثانیه چهارم از abab به abaaba می‌رود و امیدش با بدست می‌آورد.

ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.