HackerEarth Power of String problem solution YASH PAL, 31 July 2024 In this HackerEarth Power of String problem solution For a given integer K and a string S of length N, we denote the power of S, as the length of the longest substring occurring in S at least K times. Given K and S, find the power of S. HackerEarth Power of String problem solution. #include <cstdio>#include <iostream>#include <algorithm>#include <string>#include <vector>#include <cassert>using namespace std;typedef vector<int> VI;typedef long long LL;#define FOR(x, b, e) for(int x = b; x <= (e); ++x)#define FORD(x, b, e) for(int x = b; x >= (e); --x)#define REP(x, n) for(int x = 0; x < (n); ++x)#define VAR(v, n) __typeof(n) v = (n)#define ALL(c) (c).begin(), (c).end()#define SIZE(x) ((int)(x).size())#define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)#define PB push_back#define ST first#define ND second#include <set>#include <map>template<typename _T> struct SufTree { struct SufV { map<char, SufV*> sons; int p, k; bool s; _T e; SufV *par; SufV(int p, int k, SufV *par, bool s) : p(p), k(k), par(par), s(s) {} ~SufV() { FOREACH(it, sons) delete it->second; } }; struct VlP { SufV *p; char l; VlP(SufV *p, char l) : p(p), l(l) {} bool operator<(const VlP &a) const { return (a.p > p) || (a.p == p && a.l > l); } }; SufV root; string text; SufTree(const string& t) : root(0, 0, 0, 0), text(t) { map<VlP, SufV*> lnk; set<VlP> test; int len = t.length(); SufV *v = root.sons[t[len - 1]] = new SufV(len - 1, len, &root, 1); lnk[VlP(&root, t[len - 1])] = v; test.insert(VlP(&root, t[len - 1])); FORD(i, len - 2, 0) { char a = t[i]; if (!root.sons[a]) { SufV* it = v; while(it) { test.insert(VlP(it, a)); it = it->par; } it = v; lnk[VlP(it, a)] = v = root.sons[t[i]] = new SufV(i, len, &root, 1); } else { char lw; SufV *head, *head2, *x, *x1; int lw2 = 0, gl = 0; for(x = v; x != &root && test.find(VlP(x, a)) == test.end(); x = x->par) lw2 += x->k - x->p; for(x1 = x; x1 && !lnk[VlP(x1, a)]; x1 = x1->par) { gl += x1->k - x1->p; lw = t[x1->p]; } if (x1) gl--; SufV* head1 = x1 ? lnk[VlP(x1, a)] : &root; if (x == x1) head = head1; else { head2 = (!x1) ? root.sons[a] : head1->sons[lw]; head = head1->sons[t[head2->p]] = new SufV(head2->p, head2->p + 1 + gl, head1, 0); head->sons[t[head->k]] = head2; head2->p = head->k; head2->par = head; for(VAR(it, test.lower_bound(VlP(head2, 0))); it->p == head2;) test.insert(VlP(head, (it++)->l)); } for(SufV* it = v; it != x1; it = it->par) test.insert(VlP(it, a)); lnk[VlP(x, a)] = head; SufV *v1 = v; v = head->sons[t[len - lw2]] = new SufV(len - lw2, len, head, 1); lnk[VlP(v1, a)] = v; } } }};struct STLongestWord { int p, k, n; int Find(SufTree<int>::SufV& v, int d) { d += v.k - v.p; v.e = v.s; FOREACH(it, v.sons) v.e += Find(*(it->ND), d); if (v.e >= n && d > k-p) { k=v.k; p=v.k-d; } return v.e; } STLongestWord(const string& t, int n) : p(0), k(0), n(n) { SufTree<int> tr(t); Find(tr.root, 0); }};const int MINN = 1;const int MAXN = 1e6;const int MINK = 1;int main() { ios_base::sync_with_stdio(0); string s; int k, n; cin >> k >> n; assert(n >= MINN && n <= MAXN); assert(k >= MINK && k <= n); cin >> s; assert(n == s.length()); REP(i, n) assert(s[i] >= 'a' && s[i] <= 'z'); STLongestWord str(s, k); cout << str.k - str.p << endl; return 0;} Second solution #include <bits/stdc++.h>using namespace std;#define ll long longconst int MOD1 = (int)1e9 + 7;const int MOD2 = (int)1e9 + 9;const int N = (int)1e6 + 9;char s[N];struct Hash { int x, y; Hash() {} Hash(int _x, int _y) { x = _x; y = _y; } const bool operator<(Hash other) const { if (x == other.x) { return y < other.y; } return x < other.x; } const bool operator==(Hash other) const { return x == other.x && y == other.y; }};Hash add(Hash a, Hash b) { Hash res; res.x = (a.x + b.x) % MOD1; res.y = (a.y + b.y) % MOD2; return res;}Hash subtract(Hash a, Hash b) { Hash res; res.x = (a.x - b.x + MOD1) % MOD1; res.y = (a.y - b.y + MOD2) % MOD2; return res;}Hash multiply(Hash a, Hash b) { Hash res; res.x = ((ll)a.x * b.x) % MOD1; res.y = ((ll)a.y * b.y) % MOD2; return res;}Hash multiply(Hash a, int v) { Hash res; res.x = ((ll)a.x * v) % MOD1; res.y = ((ll)a.y * v) % MOD2; return res;}Hash hashes[N];Hash p[N];Hash tmp[N];int main() { int k, n; scanf("%d %dn", &k, &n); assert(1 <= n && n <= (int)1e6); assert(1 <= k && k <= n); gets(s + 1); assert(strlen(s + 1) == n); for (int i = 1; i <= n; ++i) { assert(s[i] >= 'a' && s[i] <= 'z'); } p[0] = Hash(1, 1); hashes[0] = Hash(0, 0); for (int i = 1; i <= n; ++i) { p[i] = multiply(p[i - 1], 31); hashes[i] = add(hashes[i - 1], multiply(p[i], (s[i] - 'a' + 1))); } int l = 1; int r = n; int res = 0; while (l <= r) { int m = (l + r) / 2; int sz = 0; for (int i = m; i <= n; ++i) { tmp[sz++] = multiply(subtract(hashes[i], hashes[i - m]), p[n - i]); } sort(tmp, tmp + sz); int curCnt = 1; int maxCnt = 1; for (int i = 1; i < sz; ++i) { if (tmp[i] == tmp[i - 1]) { ++curCnt; } else { maxCnt = max(curCnt, maxCnt); curCnt = 1; } } maxCnt = max(curCnt, maxCnt); if (maxCnt >= k) { res = m; l = m + 1; } else { r = m - 1; } } printf("%dn", res); return 0;} coding problems