【两 log 也能过】题解：AT_abc346_f [ABC346F] SSttrriinngg in StringString

· · 题解

我们看到这个“最大值”，再加上子序列满足单调性，所以我们可以二分。

二分一个值 k，我们依次遍历 t 串的每个字符，这个时候我们需要找 s 重复 n 遍后（设这个字符串为 S），最小的下标 j_1 满足 S_1\sim S_{j_1} 中 t_i 的数量等于 k。假设我们能求出来这个 j_1，那下次再找下一个下标 j_2，在 S_{j_1+1}\sim S_{j_2} 之间 t_{i+1} 的数量等于 k，以此往复。如果 i 还没有循环到 n，但是 j_i>n\times |s| 了，那么这个 k 值就不符合要求。

那我们怎么求这个最小的下标 j_i 呢？我们只要预处理出来每个字母在 s 中的前缀出现次数，然后再二分一下就可以了。

时间复杂度 O(|t|\log^2 (|s|n) )，需要一些卡常才能过。

AC code

#include<bits/stdc++.h>
#define ll long long
#define N 200005
#pragma GCC optimize(2)
using namespace std;
int qwq[35],l1,l2,f[35][N];
ll n;
string s,t;
ll R(ll x,int ch){
    return 1ll*qwq[ch]*(x/l1)+f[ch][x%l1];
}
bool check(ll x){
    ll lst=1;
    for(int i=1;i<=l2;++i){
        ll l=lst-1,r=l1*n,ans=-1;
        while(l<=r){
            ll mid=(l+r)>>1;
            if(R(mid,t[i]-'a')-R(lst-1,t[i]-'a')>=x)ans=mid,r=mid-1;
            else l=mid+1;
        }
        if(ans==-1)return 0;
        lst=ans+1;
    }
    return 1;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>s>>t;
    l1=s.size();l2=t.size();
    s=" "+s,t=" "+t;
    for(int i=1;i<=l1;++i){
        qwq[s[i]-'a']++;
        for(int j=0;j<26;++j){
            f[j][i]=f[j][i-1]+(s[i]==j+'a');
        }
    }
    ll l=0,r=n*l1,ans=0;
    while(l<=r){
        ll mid=(l+r)>>1;
        if(check(mid))l=mid+1,ans=mid;
        else r=mid-1;
    }
    cout<<ans;
    return 0;
}