- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۵۱۲ مگابایت
دو کلمه‌ی $s$ و $t$ به‌صورت رشته داده شده است. زیرکلمه به معنای رشته‌ای است که از حذف تعدادی (شاید هیچ) حرف از یک کلمه به‌دست می‌آید. به‌عنوان مثال، از کلمه‌ی behpardakht می‌توان زیرکلمات bera یا hard را به‌عنوان زیرکلمه در نظر گرفت ولیpardeh زیرکلمه‌ی آن نیست.
یک کلمه آینه‌ای است اگر با برعکس کردن حروف آن، همان کلمه‌ی اولیه به‌دست آید. به‌عنوان مثال، کلمات level از نوع کلمات آینه‌ای هستند.
هدف ما این است که تعیین کنیم آیا با تغییر حداکثر $k$ حرف در کلمات $s$ و یا $t$، می‌توان طول بزرگ‌ترین زیرکلمه‌ی مشترک بین $s$ و $t$ که آینه‌ای باشد را پیدا کرد. به عبارت دیگر، می‌خواهیم طول بیشینه‌ی زیرکلمه‌ای که هم در $s$ و هم در $t$ به‌عنوان زیررشته غیرمتوالی وجود داشته باشد و همچنین آینه‌ای باشد را تعیین کنیم، به شرطی که بتوانیم حداکثر $k$ حرف از هر دو کلمه را تغییر دهیم.
ورودی
در سطر اول ورودی، عدد صحیح و مثبت $k$ آمده که تعداد تغییرات را نشان می‌دهد.
$$0 \leq k \leq 60$$
در سطر دوم ورودی، رشته‌ی $s$ از حروف کوچک انگلیسی داده می‌شود. در سطر سوم ورودی، رشته‌ی $t$ از حروف کوچک انگلیسی داده می‌شود.
$$1 \leq |s|, |t| \leq 30$$
خروجی
در تنها سطر خروجی، طول بزرگ‌ترین زیررشته‌ی مشترک آینه‌ای را چاپ کنید.
مثال‌ها
ورودی نمونه ۱
3
quera
behpardakht
خروجی نمونه ۱
4
می‌توانیم با $2$ تغییر رشته quera را به aurraتبدیل کنیم. همچنین با $1$ تغییر می‌توانیم رشته behpardakht را به behparrakht تغییر دهیم. به این ترتیب در مجموع $2 + 1 = 3$ تغییر انجام دادیم و بزرگ‌ترین زیررشته‌ی پالیندروم مشترک arra می‌شود.
ورودی نمونه ۲
1
mississippis
sicilian
خروجی نمونه ۲
5
می‌توانیم با $1$ تغییر رشته sicilian را به siciliasتبدیل کنیم. بزرگ‌ترین زیررشته‌ی پالیندروم مشترک siiis می‌شود.
ارسال پاسخ برای این سؤال