NC23061 字符串

链接：https://ac.nowcoder.com/acm/problem/23061
来源：牛客网

给定两个等长的由小写字母构成的串 $A,B$，其中 $\mid A\mid =\mid B\mid =n$。

现在你需要求出一个子区间 $[l,r]$使得 $LCP(A[l,r],B[l,r])\times LCS(A[l,r],B[l,r])+LCP(A[l,r],B[l,r])+LCS(A[l,r],B[l,r])$ 最大，并输出这个值。
$LCP(S,T)$表示S和T的最长公共前缀，$LCS(S,T)$表示S和T的最长公共后缀。

aaabbbcccddd
aaaddddddddd

15

选择 $l=1,r=12$ 是一种可行的最优解。 $n<=2\ast 10^5$

思路

任何一个公共前缀本身就是一个公共后缀, 同样, 一个公共后缀也是公共前缀。 猜测：字符串的最长公共长度即是LCS和LCP的值。

证明： 设A是公共长度区间集合, B是满足题意的区间集合 显而易见, B可以左边为公共前缀, 右边为公共后缀, A只是其中一个。 但对于这两个公共前后缀来说 如果长度相等, 答案等同于任何一个。 如果长度不相等, 答案等同于其中最长的一个。

故A==B, 证毕。

代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
    string a,b;
    cin >> a >> b;
    int res= 0,ans = 0;
    for(int i = 0; i < a.size(); i++)
    {
        if(a[i] == b[i]) res++;
        else res = 0;
        ans = max(ans ,res);
    }
    cout << (long long)(ans + 1) * (ans + 1) - 1 << endl;
    return 0;
}