LCS 哈希做法

· · 个人记录

博客园。

放一个好像没人写的哈希做法。复杂度比较劣，但个人认为很简单。为什么不写 SA？因为我不会。

设两个串为 s_1,s_2，其中 s_2 为较长的一个。

发现答案必然介于 0 和 |s_1| 之间。于是我们用二分的方式枚举答案，这一步是 O(\log n) 的。

考虑对于枚举到的每个答案 k，应该如何判断是否存在长度为 k 的公共子串。下面所说“某串的子串”均默认这一子串的长度为 k。

我们发现，在任何一个串里，长度为 k 的子串至多有 O(n) 种，所以我们可以先把两个串的所有长度为 k 的子串找出来，再判断是否有一个 s_1 的子串和一个 s_2 的子串相等。要找出所有长为 k 的子串，这一步是 O(n) 的。

这里就涉及到了字符串间的比较。因此我们预处理出两个串的每个前缀的哈希值，这一步是 O(n) 的；后面每一次比较都把预处理的哈希值拿出来用即可，这一步是 O(1) 的。

这时我们发现，两两枚举两边的子串会产生 O(n^2) 次比较，总复杂度退化到 O(n^2 \log n)。这是我们不希望看到的，考虑如何降低复杂度。

容易想到开一个 unordered_map 来标记在所有 s_1 的子串中出现过的哈希值，然后将所有 s_2 的子串的哈希值遍历一遍；若某一 s_2 的子串哈希值已经出现过，那这个 k 是合法的。um 的期望复杂度是 O(1)，因此这一步是期望 O(n) 的，总复杂度期望 O(n \log n)。

然而由于 um 的神秘最坏复杂度，上面这个做法有概率退化到 O(n^2\log n)，进而 TLE。换成复杂度稳定在 O(\log n) 的 map 也没有用，因为总复杂度退化到了 O(n\log^2 n)，且常数太大。

我们忽视 gp_hash_table 这一类我不会写的东西，考虑别的做法。

我们发现双指针比较擅长将这种 O(n^2) 次的比较降到 O(n) 次。于是我们用两个 vector 存下两个串的子串的哈希值，分别排序，然后做一遍双指针即可。排序的复杂度是 O(n\log n)，两个指针至多移动 O(n) 次，因此总复杂度是 O(n\log^2 n)，略低于 10^8。

由于没有用什么常数特别大的 STL，简单卡一下常（像这样），就可以过了。

上面的文字内容应该很好懂，所以代码就不加注释了。

#pragma GCC optimize("3,Ofast,unroll-loops")
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#define ull unsigned long long
using namespace std;

const int N=2.5e5+5;

int n1,n2;
char s1[N],s2[N];

namespace sto_HASHGOD_orz{

    const ull b=1013;

    ull pw[N];
    ull val1[N],val2[N];

    inline ull mul(ull a,ull b){
        return a*b;
    }

    inline void init(){
        if(strlen(s1+1)>strlen(s2+1))swap(s1,s2);
        n1=strlen(s1+1),n2=strlen(s2+1);
        pw[0]=1;for(int i=1;i<=n2;++i)pw[i]=mul(pw[i-1],b);
        for(int i=1;i<=n1;++i)val1[i]=(mul(val1[i-1],b)+s1[i]);
        for(int i=1;i<=n2;++i)val2[i]=(mul(val2[i-1],b)+s2[i]);
        return ;
    }

    inline ull qry1(int l,int r){
        return val1[r]-mul(val1[l-1],pw[r-l+1]);
    }

    inline ull qry2(int l,int r){
        return val2[r]-mul(val2[l-1],pw[r-l+1]);
    }

}using namespace sto_HASHGOD_orz;

inline bool chk(int mid){
    vector<ull>v1,v2;
    for(int i=1;i+mid-1<=n1;++i)v1.push_back(qry1(i,i+mid-1));
    for(int i=1;i+mid-1<=n2;++i)v2.push_back(qry2(i,i+mid-1));
    sort(v1.begin(),v1.end()),sort(v2.begin(),v2.end());
    int i=0,j=0;
    while(i<v1.size()&&j<v2.size()){
        while(v1[i]<v2[j]&&i<v1.size())++i;
        while(v1[i]>v2[j]&&j<v2.size())++j;
        if(v1[i]==v2[j])return 1;
    }
    return 0;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>(s1+1);cin>>(s2+1);
    init();
    int l=0,r=n1;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(chk(mid))l=mid;
        else r=mid-1;
    }
    return cout<<r<<"\n",0;
}

/*

%%%sto       jiangly      orz%%%
%%%sto       tourist      orz%%%
%%%sto     nzhtl144777    orz%%%
%%%sto        MoTao       orz%%%
%%%sto     zhoukangyang   orz%%%
%%%sto     FanHaoqiang    orz%%%
%%%sto      ChenDanqi     orz%%%
%%%sto        hdyzyx      orz%%%
%%%sto       s_o_t_b      orz%%%
%%%sto       dottle       orz%%%
%%%sto     Social_Zhao    orz%%%
%%%sto     final_trump    orz%%%
%%%sto        stntn       orz%%%
%%%sto       zyn0309      orz%%%
%%%sto       xzy_sf       orz%%%
%%%sto      jerry1717     orz%%%
%%%sto       Statax       orz%%%
%%%sto     fengzhaoyu     orz%%%
%%%sto       XXh0919      orz%%%
%%%sto     shiziyu111     orz%%%
%%%sto      xiangxiyu     orz%%%
%%%sto      xzf110618     orz%%%
%%%sto      Lywh_ddAC     orz%%%
%%%sto      yiming1123    orz%%%
%%%sto    zhouwenbo1234   orz%%%

*/

不知道 SPOJ 怎么挂提交记录的链接，所以我就放了个图。