410196: GYM103973 F String Problem

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'$$$.

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 the length of the longest substring of $$$s$$$ in a line.

8 7
cacbabca
abcabcc

6

5 5
abcde
fdcba

4

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'.