出题人题解 | #字符串#

原题解链接：https://ac.nowcoder.com/discuss/163610

显然，我们要求的答案是$(\mathtt{\text{LCP}}(A[l,r],B[l,r])+1)\times (\mathtt{\text{LCS}}(A[l,r],B[l,r])+1)-1(\backslash texttt\{LCP\}(A[l,r],B[l,r])\; +1)\; \backslash times\; (\; \backslash texttt\{LCS\}(A[l,r],B[l,r])\; +1)-1$。

那么成为答案的那个区间一定是连续的一段$A,BA,B$两串相等的子串。否则，若我们选择的不是连续的$A,BA,B$相等的子串，那么我们可以让选择现在选择区间左右两边相等段更长的那个那段，使答案单调不劣。

#include "bits/stdc++.h"
using namespace std;
const int N = 1e6 + 10;
char S[N], T[N];
int main() {
    scanf("%s%s", S + 1, T + 1);
    int ans = 0, mx = 0;
    for(int i = 1 ; S[i] ; ++ i) {
        if(S[i] != T[i]) mx = 0;
        else ++ mx;
        ans = max(ans, mx);
    }
    printf("%lld\n", (long long) (ans + 1) * (ans + 1) - 1);
}