410196: GYM103973 F String Problem

Memory Limit:512 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. String Problemtime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Walk Alone loves strings, and he insists that a contest without a string problem is not a good contest, so here is the string problem.

You are given two strings $$$s$$$ and $$$t$$$. You need to select the longest continuous substring $$$s'$$$ from $$$s$$$, such that it is possible to reverse at most one prefix of $$$t$$$, and after that there exists a prefix of $$$t$$$ (not necessarily the same with the previous one) that equals to $$$s'$$$.

Input

The first line contains two integers $$$n\ (1\le n\le 2\cdot 10^5)$$$ and $$$m\ (1\le m\le 2\cdot 10^5)$$$, indicating the length of $$$s$$$ and $$$t$$$.

The second line and the third line are two strings consisting of only lowercase characters, representing string $$$s$$$ and $$$t$$$, respectively.

Output

Output the length of the longest substring of $$$s$$$ in a line.

ExamplesInput
8 7
cacbabca
abcabcc
Output
6
Input
5 5
abcde
fdcba
Output
4
Note

In the first example, you can reverse the prefix of length $$$4$$$ of $$$t$$$. After that $$$t$$$ becomes 'acbabcc', whose prefix of length $$$6$$$ coincides with $$$s_{1:7}$$$, i.e., 'acbabc'.

加入题单

上一题 下一题 算法标签: