Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
6.3 kB
2
Indexable
Never
#include<bits/stdc++.h>
using namespace std;
#define all(v) ((v).begin()),((v).end())
#define sz(v) (v.size())
#define yes cout<<"Yes"<<'\n';
#define no cout<<"No"<<'\n';
typedef long long ll;
typedef pair<ll,ll> pp ;
typedef vector<ll> vi;

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key oreder of key gives you the nbr of values strictly less than the value  u gave , if u want an ordered multiset change it to less or equal less_equal
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
#define int long long
ll add(ll a, ll b,ll mod){
    return (a + b) % mod;
}
ll sub(ll a, ll b,ll mod){
    return (a - b + mod) % mod;
}
ll mul(ll a, ll b,ll mod){
    return (((ll)a%mod) * ((ll)b%mod)) % mod;
}
ll bin_pow(ll n, ll k,ll mod){
    if(k == 0)return 1;
    if(k == 1)return n;
    if(k % 2 == 1) return mul(n, bin_pow(n, k - 1, mod),mod);
    ll t = bin_pow(n, k / 2,mod);
    return mul(t, t, mod);
}

ll inv_mod(ll x,ll mod)
{
    return bin_pow(x,mod-2,mod);
}

const ll N=1e6;
ll mod1=1e9+7,mod2=1e9+9;
ll b1=17301,b2=11307;
ll pow1[N];
ll inv_pow1[N];
ll pow2[N];
ll inv_pow2[N];

void prep()
{
    pow1[0]=1;
    for(int i=1;i<N;i++)
    {
        pow1[i]=mul(pow1[i-1],b1,mod1);
    }
    inv_pow1[N-1]=inv_mod(pow1[N-1],mod1);
    for(int i=N-2;i>=0;i--)
    {
        inv_pow1[i]=mul(inv_pow1[i+1],b1,mod1);
    }
    pow2[0]=1;
    for(int i=1;i<N;i++)
    {
        pow2[i]=mul(pow2[i-1],b2,mod2);
    }
    inv_pow2[N-1]=inv_mod(pow2[N-1],mod2);
    for(int i=N-2;i>=0;i--)
    {
        inv_pow2[i]=mul(inv_pow2[i+1],b2,mod2);
    }
}
const int sz=3e5;
ll h[sz],h1[sz];
pair<ll,ll> hashing(string &t)
{
    ll p=0;
    for(int i=0;i<t.size();i++)
    {
        p=add(p,mul(pow1[i],t[i]-'a',mod1),mod1);
        h[i]=p;
    }
    ll q=0;
    for(int i=0;i<t.size();i++)
    {
        q=add(q,mul(pow2[i],t[i]-'a',mod2),mod2);
        h1[i]=q;
    }
    return {p,q};
}

pair<ll,ll> add_begin(pair<ll,ll> p,char t)
{
    // add a single char to the hashing of the string at the beginning
    return {add(t-'a',mul(p.first,b1,mod1),mod1),add(t-'a',mul(p.second,b2,mod2),mod2)};
}

pair<ll,ll> remove_begin(pair<ll,ll> p,char t)
{
    // remove the char t from the beginning of the string
    return {mul(sub(p.first,t-'a',mod1),inv_pow1[1],mod1),mul(sub(p.second,t-'a',mod2),inv_pow2[1],mod2)};
}

pair<ll,ll> remove_begin_string(pair<ll,ll> p,pair<ll,ll> p1,ll len)
{
    // remove the string corresponding to the hashing p1 and the length len from the beginning of the string
    return {mul(sub(p.first,p1.first,mod1),inv_pow1[len-1],mod1),mul(sub(p.second,p1.second,mod2),inv_pow2[len-1],mod2)};
}

pair<ll,ll> add_end(pair<ll,ll> p,ll len,char t)// len is the length of the string
{
    // add a single char to the hashing of the string at the end
    return {add(p.first,mul(t-'a',pow1[len-1],mod1),mod1),add(p.second,mul(t-'a',pow2[len-1],mod2),mod2)};
}

pair<ll,ll> remove_end(pair<ll,ll> p,ll len,char t)
// len is the length of the string
{
    // remove a single char to the hashing of the string at the end
    return {sub(p.first,mul(t-'a',pow1[len-1],mod1),mod1),sub(p.second,mul(t-'a',pow2[len-1],mod2),mod2)};
}
pair<ll,ll> remove_end_string(pair<ll,ll> p,pair<ll,ll> p1,ll len)
{

    return {sub(p.first,p1.first,mod1),sub(p.second,p1.second,mod2)};
}

pair<ll,ll>gethash(int i,int j)
{
    if (i==0)
    {
        return {h[j],h1[j]};
    }
    int res1=((h[j]-h[i-1])%mod1+mod1)%mod1,res2=((h1[j]-h1[i-1])%mod2+mod2)%mod2;
    res1=res1*inv_pow1[i];
    res2=res2*inv_pow2[i];
    res1%=mod1;
    res2%=mod2;
    return {res1,res2};


}

pair<ll,ll> merge_strings(pair<ll,ll> p1,pair<ll,ll> p2,ll len1)//p1 is the hashing of the first string // p2 is the hashing of the second string // len1 is the length of the first string
{
    // merge_strings concatinate the hashing of two strings
    return {add(p1.first,mul(p2.first,pow1[len1],mod1),mod1),add(p1.second,mul(p2.second,pow2[len1],mod2),mod2)};
}



set<ll>s;
const ll mod=1e18;
void add_divs(ll x, map<ll, ll>&divs){
    ll i = 2;
    while(i * i <= x){
        while (x % i == 0){
            divs[i]++;
            x /= i;
        }
        i++;
    }
    if(x > 1) divs[x]++;
}
string cv3(ll n)
{
    string ch="";
    if (n==0)
    {
        return "0";
    }
    while(n>=1)
    {
        char c='0'+(n%3);
        ch=c+ch;
        n/=3;
    }
    return ch;
}

const int N1=1e6+5;
bool prime[N1 + 1];
void sieve()
{
    int n=1e6;
    memset(prime, true, sizeof(prime));
    for (int p = 2; p * p <= n; p++) {

        if (prime[p] == true) {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
}
bool comp(pp p1,pp p2)
{
    if (p2.second==p1.second)
        return (p1.first>p2.first);
    return (p2.second>p1.second);
}
struct cmp {
    bool operator() (const pp &a, const pp&b)  const{
        return (a.second>b.second);
    }
};
void solve()
{
    int n,l1,r1;
    cin>>n>>l1>>r1;
    ll k=l1;
    string ch;
    cin>>ch;
    pp p=hashing(ch);
    ll l=1,r=n,mid,ans=0;
    while(l<=r)
    {
        mid=(l+r)/2;
        ll d=1;
        int i=0;
       ll p1=i+mid;
       pp c=gethash(i,mid-1);
       while(p1+mid-1<=n-1)
       {
           pp c1=gethash(p1,p1+mid-1);
           if (c1==c)
           {
               p1=p1+mid;
               d++;
           }
           else
               p1++;
       }
       if (d>=l1)
       {
           ans=mid;
           l=mid+1;
       }
       else
           r=mid-1;

    }
    cout<<ans<<endl;

}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t;
    prep();
    //   freopen("cowdance.in", "r", stdin);
    // freopen("cowdance.out", "w", stdout);
    t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
// cout << setprecision(10) << fixed;
//check corner cases before submission
}
Leave a Comment