字符串、哈希

子串哈希，维护前缀哈希值和后缀哈希值，计算删除每两个位置后的哈希值并统计数量。

为防止被卡写了三哈希，判重用了 map 所以时间复杂度是 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
template<int mod,int bas>
struct Hashtable{
    int n,f[200'005],fac[200'005];
    Hashtable(){
        static constexpr int lim=200'000;
        fac[0]=1;
        for(int i=1;i<=lim;i++) fac[i]=1ll*fac[i-1]*bas%mod;
    }
    void loadhash(const string &s){
        n=s.size()-1;
        for(int i=1;i<=n;i++) f[i]=(1ll*f[i-1]*bas+s[i]-'a'+1)%mod;
    }
    int hashval(int l,int r){
        return (f[r]-1ll*f[l-1]*fac[r-l+1]%mod+mod)%mod;
    }
    int vso(int l,int r){
        if(l<1) return hashval(r,n);
        if(r>n) return hashval(1,l);
        return (1ll*hashval(1,l)*fac[n-r+1]+hashval(r,n))%mod;
    }
};
Hashtable<1'000'000'009,37> a;
Hashtable<1'000'000'007,97> b;
Hashtable<998'244'353,41> c;
int n,ans;
string s;
void solution(){
    cin>>n>>s,ans=0,s='#'+s;
    a.loadhash(s),b.loadhash(s),c.loadhash(s);
    map<int,map<int,map<int,bool>>> m;
    for(int i=1,l=0,r=3;i<=n-1;i++,l++,r++){
        auto &it=m[a.vso(l,r)][b.vso(l,r)][c.vso(l,r)];
        if(!it) it=1,++ans;
    }
    cout<<ans<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}