yaohaoyou

题目传送器

更爽的阅读体验

前言

为什么都用 PAM 和 子序列自动机，我会二分答案 + manacher + Hash。

题意

自行看题。

做法

推一下式子即可，$pre_i$ 表示 $i$ 的前缀。

$Rev(lcs(i,j)) = LCP(Rev(pre_i),Rev(pre_j))$

手模一下样例就能发现其实就是求以 $i$ 为中心的回文半径和以 $j$ 为中心的回文半径的 $\text{LCP}$。

显然答案是有二分性的，可以二分答案 $x$ 后将每个位置 $i$ 对应的 $[i-x+1,i]$ 的哈希值放入 map 或 unordered_map 中，只要有相同的就返回 true。

manacher 只需要跑以当前点为中心的回文串即可，不用在相邻两位加入字符。

AC Code

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int maxn=1e6+10,base=31;
int n,p[maxn];
ull hsh[maxn],bs[maxn];
string s;
unordered_map<ull,bool> mp;  // 记录是否出现过的哈希值
inline ull Hash(int l,int r){return hsh[r]-hsh[l-1]*bs[r-l+1];}
inline bool check(int x){
    mp.clear();
    for(int i=1;i<=n;i++){
        if(p[i]<x)  continue;
        if(mp[Hash(i-x+1,i)])    return true;
        mp[Hash(i-x+1,i)]=true;
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>s;
    s='|'+s+'#';
    bs[0]=1;
    for(int i=1;i<=n;i++){
        hsh[i]=hsh[i-1]*base+(s[i]-'a');
        bs[i]=bs[i-1]*base;
    }
    // manacher
    for(int i=1,mid=0,r=0;i<=n;i++){
        p[i]=i>r?1:min(p[(mid<<1)-i],r-i+1);
        while(s[i+p[i]]==s[i-p[i]]) p[i]++;
        if(i+p[i]>r){r=i+p[i]-1;mid=i;}
    }
    // 二分答案
    int l=1,r=n,ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)){ans=mid;l=mid+1;}
        else    r=mid-1;
    }
    printf("%d\n",ans);
}

总结 & 乱搞

时间复杂度为 $O(n \times \log_2n)$，跑得还挺快。实测不使用哈希，直接将字符串区间放入 unordered_map，也就是 $O(n^2\times \log_2n)$ 也能过，只用 300+ms。