+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- دو کلمه‌ی $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` می‌شود.

حل سؤال در بانک سؤالات