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


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 long
const 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 %d\n", &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("%d\n", res);
return 0;
}