题解：UVA10829 L-Gap Substrings

SFlyer · 2024-12-30 19:45:45 · 题解

首先发现不固定长度是困难的，所以应该枚举长度。但是如果这样了，还是得枚举起始点啊，怎么办？那么尝试看看开始位置在 i\sim i+len-1 之间的能不能统一计算？

由于我脑子不好，所以先讲讲我的假做法和蒸馍修正。考虑一个 |...|...|...| 的东东，我们枚举开始位置是什么区间，考虑是 [...].[.|.].| 这种区间。那么我们发现如果这个是合法的，|[..|].[|..]| 是合法的如果下一位也是相等的。这说明啥？这说明如果 i\sim i+len-1 中发现了第一次合法的，那么从他开始有一个区间是合法的，然后又不合法了。那么我们的合法性是 xxxxoooxxxxx 这种结构的。

发现这个求出区间就是困难的事情啊。但是这种区间也是很通用的，就是所有满足的涵盖一个位置的区间也是连续的。

然后发现了一个重要的性质：所有 i\sim i+len-1 开头的区间一定涵盖 i+k-1。那么就好做了啊！二分+哈希求出开始，结束合法位置即可。

时间复杂度 \mathcal{O}(n\log^2 n)。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e5+5;
const ll B = 37;
const ll mod = 998244353;

int n,k;
string s;
ll pw[N],hs[N];

ll qy(ll l,ll r){
    return (hs[r]-hs[l-1]*pw[r-l+1]%mod+mod)%mod;
}

int lcs(int a,int b){
    int l=0,r=min(a,b)+1;
    while (l+1<r){
        int mid=l+r>>1;
        if (qy(a-mid+1,a)==qy(b-mid+1,b)) l=mid;
        else r=mid;
    }
    return l;
}

int lcp(int a,int b){
    int l=0,r=n-b+2;
    while (l+1<r){
        int mid=l+r>>1;
        if (qy(a,a+mid-1)==qy(b,b+mid-1)) l=mid;
        else r=mid;
    }
    return l;
}

int tc;

void solve(){
    cin>>k>>s;
    n=s.size();
    s=" "+s;
    for (int i=1; i<=n; i++){
        hs[i]=(hs[i-1]*B%mod+s[i]-'a'+1)%mod;
    }
    ll ans=0;
    for (int l=1; l<=n; l++){
        for (int i=l; i+l+k<=n; i+=l){
            int j=i+l+k;
            if (s[i]!=s[j]) continue;
            int lb=lcs(i,j),rb=lcp(i,j);
            lb=min(lb,l);
            rb=min(rb,l);
            if (lb+rb-1>=l) ans+=lb+rb-l;
        }
    }
    cout<<"Case "<<++tc<<": "<<ans<<"\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    pw[0]=1;
    for (int i=1; i<N; i++) pw[i]=pw[i-1]*B%mod;
    int t;
    cin>>t;
    while (t--){
        solve();
    } 
    return 0;
}