题解：CF2010C2 Message Transmission Error (hard version)

· · 题解

题目大意

给你一个字符串 s。求是否有字符串 t 既是 s 的前缀又是 s 的后缀，并且 t 的长度大于 s 的一半。

题目做法

我们如果暴力枚举发现时间复杂度是 O(n^2) 这样的复杂度明显不能接受。

做法

先求出字符串 s 的最长公共前后缀的长度，我们将它叫做 h，如果 t \times 2 比 s 的长度大，就是满足了长度大于 s 的一半这个条件，那么原来的字符串就是答案。

为什么

当条件满足的时候，那么 s 的最长公共前后缀就有相交的部分，相交的地方就是原串发生合并的地方，所以可以知道原串就是 s 的最长公共前后缀。

给出代码

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int n,d;
int ans;
int a[N];
int main(){
    scanf("%d%d",&n,&d);
    for(int i=1; i<=n; i++){
        scanf("%d",&a[i]);
    }
    for(int i=1; i<=n; i++){
        int l=lower_bound(a+1,a+n+1,a[i]-d)-a;
        int r=upper_bound(a+1,a+n+1,a[i]+d)-a-1;
        ans+=(3*i-2*l-r+1)*(r-i)/2;
    }
    printf ("%d\n",ans);
    return 0;
}