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

zzzyyyyhhhhh · 2025-02-13 17:17:43 · 题解

因为是 python 题，所以 c++ 可以爆草，并且现有题解都是 c++ 题解。

首先这题可以二分加哈希得到答案，难点在于如何用哈希判断两串是否是同类串。

因为要解决的是同类串问题，两种字符之间的关系只有相同和不同。我们把每一种字符单独拿出来按所在位置分别哈希得到一个集合，两个串同类当且仅当对应集合相同。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N =1e5+100,base=19260817,mod=1e9+7;
int n,m,qpow[N],p[N],h[26],cnt[26],ls[26],tmp[26];
char a[N],b[N];
struct hashh
{
    inline int operator()(const pair<int,int> x)const
    {
        return x.first^x.second^(x.first>>5ll);
    }
};
unordered_set<pair<int,int>,hashh> s;
inline pair<int,int> add()
{
    unsigned long long res=0;
    unsigned long long k=0;
    for(int i=0;i<26;i++)tmp[i]=h[i];
    sort(tmp,tmp+26);
    for(int i=0;i<26;i++)res=res*998244853+tmp[i],k=k*998244353+tmp[i];
    return {res+k,res^k};
}
inline bool check(int x)
{
    s.clear();
    for(int i=0;i<26;i++)ls[i]=h[i]=cnt[i]=0;
    for(int i=1;i<=x;i++)h[a[i]]=(h[a[i]]*base+i-ls[a[i]])%mod,cnt[a[i]]++,ls[a[i]]=i;
    s.insert(add());
    for(int i=x+1;i<=n;i++)
    {
        for(int j=0;j<26;j++)if(cnt[j]){h[j]+=mod-qpow[cnt[j]-1];if(h[j]>=mod)h[j]-=mod;}
        cnt[a[i-x]]--,cnt[a[i]]++;
        h[a[i]]=(h[a[i]]*base+i-max(ls[a[i]],i-x))%mod,ls[a[i]]=i;
        s.insert(add());
    }

    for(int i=0;i<26;i++)ls[i]=h[i]=cnt[i]=0;
    for(int i=1;i<=x;i++)h[b[i]]=(h[b[i]]*base+i-ls[b[i]])%mod,cnt[b[i]]++,ls[b[i]]=i;
    if(s.find(add())!=s.end())return 1;
    for(int i=x+1;i<=m;i++)
    {
        for(int j=0;j<26;j++)if(cnt[j]){h[j]+=mod-qpow[cnt[j]-1];if(h[j]>=mod)h[j]-=mod;}
        cnt[b[i-x]]--,cnt[b[i]]++;
        h[b[i]]=(h[b[i]]*base+i-max(ls[b[i]],i-x))%mod,ls[b[i]]=i;
        if(s.find(add())!=s.end())return 1;
    }
    return 0;
}
signed main()
{
    int st=clock();
    cin>>(a+1)>>(b+1);
    n=strlen(a+1),m=strlen(b+1);
    for(int i=1;i<=n;i++)a[i]-='a';
    for(int i=1;i<=m;i++)b[i]-='a';
    int l=1,r=min(n,m),mid,ans=1;
    qpow[0]=p[0]=1;
    for(int i=1;i<=r;i++)qpow[i]=qpow[i-1]*base%mod;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(mid))ans=mid,l=mid+1;
        else r=mid-1;
    }
    cout<<ans<<'\n';
    cerr<<(double)(clock()-st)/CLOCKS_PER_SEC;
}