题解：P10992 [蓝桥杯 2023 国 Python A] 最长同类子串

· · 题解

Solution

「同类串」的定义为对于两个等长的字符串 s 和 t，所有位置上的字符都互相对应。目标是找出一个尽可能大的 k 使得 s, t 分别含有一个长度为 k 的子串 s', t'，且 s',t' 是「同类串」。

直接进行字符串哈希很难做。注意到答案 k 具有单调性，我们可以进行二分答案将该问题转化为判断性问题。

从「同类串」的定义出发，所有字符出现位置相互对应和所有位置上的字符互相对应显然是等价的。

那我们不妨从字符出现的位置入手。

进一步地，两个为一组「同类串」的字符串里的所有字符上一次出现的位置一定相同。

故存下每一个位置上一个出现该位置上的字符的位置，判断两个字符串中是否存在长度固定的区间里所有字符上一次出现的位置相同。

使用哈希维护一个滑动窗口，每次滑动单位长度 1 的长度。设当前的固定长度为 k，滑动到的左端点为 i。可以提前预处理出字符上一次出现的位置、下一次出现该字符的位置，以做到 \mathcal{O}(1) 地从上一个 [i-1,i+k-2] 的窗口滑动到 [i,i+k-1] 的窗口。

故判断函数可以 \mathcal{O}(n) 解决。总时间复杂度为 \mathcal{O}(n\log n)。

Code

/* ChongYun */
#include<bits/stdc++.h>
#define START_LL 0
using namespace std;
#define start(x) using namespace x
#if START_LL
#define int long long
#endif
#define ull unsigned long long
namespace IO{
    inline int read(){
        register int x=0,f=1;
        register char ch=getchar();
        while(ch<'0'||ch>'9'){
            if(ch=='-') f=-1;
            ch=getchar();
        }
        while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
        return x*f;
    }
    inline void write(int x){
        if(x<0) x=-x,putchar('-');
        if(x>9) write(x/10);
        putchar((x%10)^48);
    }
    inline void write(int x,char ch){ write(x),putchar(ch); }
    inline int read(string &Str){
        char ch=getchar(); Str=" ";
        while(ch<'a'||ch>'z') ch=getchar();
        while(ch>='a'&&ch<='z') Str+=ch,ch=getchar();
        return Str.size()-1;
    }
    inline void write(string Str){ register int i=0,__=Str.size(); while(i<__) putchar(Str[i]),++i; }
    inline void write(string Str,char ch){ write(Str),putchar(ch); }
}start(IO);
const int N=1e5+5,Sigma=123;
int n,m,B;
string S,T;
ull base=1e5+3,pw[N],HashS[N],HashT[N];
int lstS[130],lstT[130],nowS[N],nowT[N],nxtS[N],nxtT[N];
unordered_map<ull,bool> vis;
void reHash(){ pw[0]=1; for(int i=1;i<=max(n,m);i++) pw[i]=pw[i-1]*base; }
bool check(int x){
    vis.clear(); ull res=0;
    for(int i=0;i<Sigma;++i) lstS[i]=lstT[i]=0;
    for(int i=1;i<=n;++i) nxtS[i]=0,nowS[i]=B;
    for(int i=1;i<=m;++i) nxtT[i]=0,nowT[i]=B;
    for(int i=1;i<=n;++i){ if(lstS[S[i]]) nxtS[lstS[S[i]]]=i,nowS[i]=i-lstS[S[i]]; lstS[S[i]]=i; }
    for(int i=1;i<=m;++i){ if(lstT[T[i]]) nxtT[lstT[T[i]]]=i,nowT[i]=i-lstT[T[i]]; lstT[T[i]]=i; }
    for(int i=1;i<=x;++i) res=res*base+nowS[i];
    vis[res]=1;
    for(int i=2,len;i+x-1<=n;++i){
        res=(res-nowS[i-1]*pw[x-1])*base+nowS[i+x-1];
        if(nxtS[i-1]){
            len=i+x-1-nxtS[i-1];
            if(nxtS[i-1]<=n){
                ull old=nowS[nxtS[i-1]]*pw[len];
                nowS[nxtS[i-1]]=B;
                if(nxtS[i-1]<=i+x-1) res-=old,res+=B*pw[len];
            }
        }
        vis[res]=1;
    }
    res=0;
    for(int i=1;i<=x;++i) res=res*base+nowT[i];
    if(vis[res]) return 1;
    for(int i=2,len;i+x-1<=m;++i){
        res=(res-nowT[i-1]*pw[x-1])*base+nowT[i+x-1];
        if(nxtT[i-1]){
            len=i+x-1-nxtT[i-1];
            if(nxtT[i-1]<=m){
                ull old=nowT[nxtT[i-1]]*pw[len];
                nowT[nxtT[i-1]]=B;
                if(nxtT[i-1]<=i+x-1) res-=old,res+=B*pw[len];
            }
        }
        if(vis.find(res)!=vis.end()) return 1;
    }
    return 0;
}
signed main(){
    n=read(S),m=read(T); 
    reHash(),B=max(n,m)+1;
    int l=1,r=min(n,m),mid,ans;
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid)) l=mid+1,ans=mid;
        else r=mid-1;
    } 
    write(ans);
    return 0;
}

2025.11.12 upd：突然翻到了这题，更新了一下实现。umap 显著提升了速度，虽然常数大但也比 map 快很多。时间复杂度 \mathcal{O}(n\log n)。