Untitled
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