この問題は、Z algorithm と呼ばれるアルゴリズムを使うことで解くことができます。

Z algorithm を使うと、長さ \(n\) の文字列 \(s\) について、次の \(n\) 個の値を \(O(n)\) 時間ですべて求めることができます。

\(s\) と、\(s\) の先頭 \(i\) 文字を取り除いた文字列との最長共通接頭辞の長さ \((0\le i\lt n)\)

Z algorithm を使う文字列をうまく設計することで、この問題を解くことを考えます。

\(S\) と \(T\) をこの順に連結した文字列 \(S+T\) に対して Z algorithm を使うことを考えます。 整数 \(1\le i\le L\) について \(S+T\) の末尾 \(i\) 文字と先頭 \(i\) 文字が一致しているとき（つまり、最長共通接頭辞の長さが \(i\) のとき）、\(S\) の先頭 \(i\) 文字と \(T\) の末尾 \(i\) 文字が一致していることがわかります。 よって、\(S+T\) に対して Z algorithm を実行したのち、\(O(L)\) 時間かけて右側接合の最大の幅を求めることができます。

また、\(T\) と \(S\) をこの順に連結した文字列 \(T+S\) に対しても同様にすることで左側接合の最大の幅を求めることができます。

時間計算量は \(O(M+L)\) となります。

実装例は以下のようになります。

#include <iostream>
#include <atcoder/string>
using namespace std;

int main() {
    int L, M;
    cin >> L >> M;
    string S, T;
    cin >> S >> T;
    vector<int> left = atcoder::z_algorithm(T + S), right = atcoder::z_algorithm(S + T);
    for (int i = L; i > 0; --i) {
        if (left[L + M - i] >= i || right[L + M - i] >= i) {
            cout << i << endl;
            return 0;
        }
    }
    cout << 0 << endl;
    return 0;
}

from atcoder.string import z_algorithm


L, M = map(int, input().split())
S = input()
T = input()

left = z_algorithm(T + S)
right = z_algorithm(S + T)
for i in range(L, 0, -1):
    if left[-i] >= i or right[-i] >= i:
        print(i)
        break
else:
    print(0)