Table of Contents
Build a String – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Build a String HackerRank Solution
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
template<typename Val, typename Compare = std::less<Val>, int BlockSize = 10>
class DirectRMQ {
public:
typedef int Index;
typedef char InBlockIndex;
typedef InBlockIndex(*BlockTypeRef)[BlockSize];
DirectRMQ(Compare comp_ = Compare()) :
blockTypes(0), innerBlockTable(0), sparseTable(0) {
comp = comp_;
calcBallotNumbers();
buildInnerBlockTable();
}
~DirectRMQ() {
delete[] innerBlockTable;
delete[] blockTypes; delete[] sparseTable;
}
void build(const Val *a, Index n) {
blocks = (n + BlockSize - 1) / BlockSize;
stHeight = 0; while(1 << stHeight < blocks) ++ stHeight;
delete[] blockTypes; delete[] sparseTable;
blockTypes = new BlockTypeRef[blocks];
calcBlockTypes(a, n);
buildInnerBlockTable(a, n);
sparseTable = new Index[blocks * stHeight];
buildSparseTable(a);
}
Index query(const Val *a, Index l, Index r) const {
Index x = l / BlockSize, y = r / BlockSize, z = y - x;
if(z == 0) return x * BlockSize + blockTypes[x][l % BlockSize][r % BlockSize];
if(z == 1) return assumeleft_minIndex(a,
x * BlockSize + blockTypes[x][l % BlockSize][BlockSize - 1],
y * BlockSize + blockTypes[y][0][r % BlockSize]);
z -= 2;
Index k = 0, s;
s = ((z & 0xffff0000) != 0) << 4; z >>= s; k |= s;
s = ((z & 0x0000ff00) != 0) << 3; z >>= s; k |= s;
s = ((z & 0x000000f0) != 0) << 2; z >>= s; k |= s;
s = ((z & 0x0000000c) != 0) << 1; z >>= s; k |= s;
s = ((z & 0x00000002) != 0) << 0; z >>= s; k |= s;
return assumeleft_minIndex(a
, assumeleft_minIndex(a,
x * BlockSize + blockTypes[x][l % BlockSize][BlockSize - 1],
sparseTable[x + 1 + blocks * k])
, assumeleft_minIndex(a,
sparseTable[y + blocks * k - (1 << k)],
y * BlockSize + blockTypes[y][0][r % BlockSize])
);
}
Val queryVal(const Val *a, Index l, Index r) const {
Index x = l / BlockSize, y = r / BlockSize, z = y - x;
if(z == 0) return a[x * BlockSize + blockTypes[x][l % BlockSize][r % BlockSize]];
Val edge = minVal(
a[x * BlockSize + blockTypes[x][l % BlockSize][BlockSize - 1]],
a[y * BlockSize + blockTypes[y][0][r % BlockSize]]);
if(z == 1) return edge;
z -= 2;
Index k = 0, s;
s = ((z & 0xffff0000) != 0) << 4; z >>= s; k |= s;
s = ((z & 0x0000ff00) != 0) << 3; z >>= s; k |= s;
s = ((z & 0x000000f0) != 0) << 2; z >>= s; k |= s;
s = ((z & 0x0000000c) != 0) << 1; z >>= s; k |= s;
s = ((z & 0x00000002) != 0) << 0; z >>= s; k |= s;
return minVal(edge, minVal(
a[sparseTable[x + 1 + blocks * k]],
a[sparseTable[y + blocks * k - (1 << k)]]));
}
private:
Compare comp;
int ballotNumbers[BlockSize + 1][BlockSize + 1];
InBlockIndex(*innerBlockTable)[BlockSize][BlockSize];
Index blocks;
int stHeight;
BlockTypeRef *blockTypes;
Index *sparseTable;
inline Index minIndex(const Val *a, Index x, Index y) const {
return comp(a[x], a[y]) || (a[x] == a[y] && x < y) ? x : y;
}
inline Index assumeleft_minIndex(const Val *a, Index x, Index y) const {
return comp(a[y], a[x]) ? y : x;
}
inline Val minVal(Val x, Val y) const {
return comp(y, x) ? y : x;
}
void buildSparseTable(const Val *a) {
Index *b = sparseTable;
if(stHeight) for(Index i = 0; i < blocks; i ++)
b[i] = i * BlockSize + blockTypes[i][0][BlockSize - 1];
for(Index t = 1; t * 2 < blocks; t *= 2) {
std::memcpy(b + blocks, b, blocks * sizeof(Index));
b += blocks;
for(Index i = 0; i < blocks - t; ++ i)
b[i] = assumeleft_minIndex(a, b[i], b[i + t]);
}
}
void buildInnerBlockTable(const Val *a, Index n) {
for(Index i = 0; i < blocks; i ++) {
BlockTypeRef table = blockTypes[i];
if(table[0][0] != -1) continue;
const Val *p = getBlock(a, n, i);
for(InBlockIndex left = 0; left < BlockSize; left ++) {
Val minV = p[left];
InBlockIndex minI = left;
for(InBlockIndex right = left; right < BlockSize; right ++) {
if(comp(p[right], minV)) {
minV = p[right];
minI = right;
}
table[left][right] = minI;
}
}
}
}
const Val *getBlock(const Val *a, Index n, Index i) {
Index offset = i * BlockSize;
if(offset + BlockSize <= n)
return a + offset;
else {
static Val tmp_a[BlockSize];
std::copy(a + offset, a + n, tmp_a);
Val maxVal = Val();
for(Index j = i; j < n; j ++)
if(comp(maxVal, a[j])) maxVal = a[j];
std::fill(tmp_a + (n - offset), tmp_a + BlockSize, maxVal);
return tmp_a;
}
}
void calcBlockTypes(const Val *a, Index n) {
Val tmp_rp[BlockSize + 1];
for(Index i = 0; i < blocks; i ++)
blockTypes[i] = calcBlockType(getBlock(a, n, i), tmp_rp);
}
BlockTypeRef calcBlockType(const Val *a, Val *rp) {
int q = BlockSize, N = 0;
for(int i = 0; i < BlockSize; i ++) {
while(q + i - BlockSize > 0 && comp(a[i], rp[q + i - BlockSize])) {
N += ballotNumbers[BlockSize - i - 1][q];
q --;
}
rp[q + i + 1 - BlockSize] = a[i];
}
return innerBlockTable[N];
}
void calcBallotNumbers() {
for(int p = 0; p <= BlockSize; p ++) {
for(int q = 0; q <= BlockSize; q ++) {
if(p == 0 && q == 0)
ballotNumbers[p][q] = 1;
else if(p <= q)
ballotNumbers[p][q] =
(q ? ballotNumbers[p][q - 1] : 0) +
(p ? ballotNumbers[p - 1][q] : 0);
else
ballotNumbers[p][q] = 0;
}
}
}
void buildInnerBlockTable() {
int numberOfTrees = ballotNumbers[BlockSize][BlockSize];
innerBlockTable = new InBlockIndex[numberOfTrees][BlockSize][BlockSize];
for(int i = 0; i < numberOfTrees; i ++)
innerBlockTable[i][0][0] = -1;
}
};
class SuffixArray {
public:
typedef char Alpha;
typedef int Index;
void build(const Alpha *str, Index n, int AlphaSize);
void build(const Alpha *str, Index n);
void buildAll(const Alpha *str, Index n);
inline Index getKThSuffix(Index k) const { return suffixArray[k]; }
inline Index length() const { return static_cast<Index>(suffixArray.size() - 1); }
std::vector<Index> suffixArray;
template<typename AlphaT> void sa_is(const AlphaT *str, Index n, int AlphaSize, Index *sa, std::vector<Index> &bucketOffsets);
template<typename AlphaT> void inducedSort(const AlphaT *str, Index n, int AlphaSize, const std::vector<bool> &types, Index *sa, std::vector<Index> &bucketOffsets);
template<typename AlphaT> void countAlphabets(const AlphaT *str, Index n, int AlphaSize, std::vector<Index> &bucketOffsets, bool b = false);
template<typename AlphaT> void getBucketOffsets(const AlphaT *str, Index n, bool dir, int AlphaSize, std::vector<Index> &bucketOffsets);
void buildInverseSuffixArray();
std::vector<Index> inverseSuffixArray;
void computeLCPArray(const Alpha *str);
std::vector<Index> lcpArray;
typedef DirectRMQ<Index> LCPArrayRMQ;
LCPArrayRMQ lcpArrayRMQ;
void preprocessLCPArrayRMQ() {
lcpArrayRMQ.build(&lcpArray[0], length() + 1);
}
Index computeLCP(Index i, Index j) const;
};
void SuffixArray::build(const Alpha *str, Index n, int AlphaSize) {
suffixArray.resize(n + 1);
if(n == 0) suffixArray[0] = 0;
else {
std::vector<Index> bucketOffsets(std::max(AlphaSize, (n + 1) / 2) + 1);
sa_is<Alpha>(str, n, AlphaSize, &suffixArray[0], bucketOffsets);
}
}
void SuffixArray::build(const Alpha *str, Index n) {
Alpha maxElem = *std::max_element(str, str + n);
assert(maxElem + 0 < std::numeric_limits<int>::max());
build(str, n, (int)(maxElem + 1));
}
void SuffixArray::buildAll(const Alpha *str, Index n) {
build(str, n);
buildInverseSuffixArray();
computeLCPArray(str);
preprocessLCPArrayRMQ();
}
template<typename AlphaT>
void SuffixArray::sa_is(const AlphaT *str, Index n, int AlphaSize, Index *sa, std::vector<Index> &bucketOffsets) {
std::vector<bool> types(n + 1);
types[n - 1] = 0; types[n] = 1;
for(Index i = n - 2; i >= 0; i --)
types[i] = str[i] < str[i + 1] || (str[i] == str[i + 1] && types[i + 1]);
countAlphabets(str, n, AlphaSize, bucketOffsets);
getBucketOffsets(str, n, true, AlphaSize, bucketOffsets);
std::fill(sa, sa + n + 1, -1);
for(Index i = 1; i < n; i ++)
if(types[i] && !types[i - 1]) sa[-- bucketOffsets[(int)str[i]]] = i;
sa[0] = n;
inducedSort(str, n, AlphaSize, types, sa, bucketOffsets);
Index n1 = 0;
for(Index i = 0; i <= n; i ++) {
Index j = sa[i];
if(j > 0 && types[j] && !types[j - 1]) sa[n1 ++] = j;
}
Index *buffer = sa + n1;
std::fill(buffer, sa + n + 1, -1);
Index uniqueLMSCount = 0, prevPos = -1;
assert(sa[0] == n);
buffer[sa[0] / 2] = uniqueLMSCount ++; //'$'
for(Index i = 1; i < n1; i ++) {
Index pos = sa[i]; bool diff = false;
if(prevPos == -1) diff = true;
else for(Index j = pos, k = prevPos; ; j ++, k ++) {
if(str[j] != str[k] || types[j] != types[k]) {
diff = true;
break;
} else if(j != pos && ((types[j] && !types[j - 1]) || (types[k] && !types[k - 1])))
break;
}
if(diff) {
uniqueLMSCount ++;
prevPos = pos;
}
buffer[pos / 2] = uniqueLMSCount - 1;
}
for(Index i = n, j = n; i >= n1; i --)
if(sa[i] >= 0) sa[j --] = sa[i];
Index *sa1 = sa, *s1 = sa + n + 1 - n1;
if(uniqueLMSCount == n1)
for(Index i = 0; i < n1; i ++) sa1[s1[i]] = i;
else
sa_is<Index>(s1, n1 - 1, uniqueLMSCount, sa1, bucketOffsets);
countAlphabets(str, n, AlphaSize, bucketOffsets);
getBucketOffsets(str, n, true, AlphaSize, bucketOffsets);
for(Index i = 1, j = 0; i <= n; i ++)
if(types[i] && !types[i - 1]) s1[j ++] = i;
for(Index i = 0; i < n1; i ++) sa1[i] = s1[sa1[i]];
std::fill(sa + n1, sa + n + 1, -1);
for(Index i = n1 - 1; i >= 1; i --) {
Index j = sa[i]; sa[i] = -1;
sa[-- bucketOffsets[(int)str[j]]] = j;
}
inducedSort(str, n, AlphaSize, types, sa, bucketOffsets);
}
template<typename AlphaT>
void SuffixArray::inducedSort(const AlphaT *str, Index n, int AlphaSize, const std::vector<bool> &types, Index *sa, std::vector<Index> &bucketOffsets) {
getBucketOffsets(str, n, false, AlphaSize, bucketOffsets);
for(Index i = 0; i < n; i ++) {
Index j = sa[i] - 1;
if(j >= 0 && !types[j]) sa[bucketOffsets[(int)str[j]] ++] = j;
}
getBucketOffsets(str, n, true, AlphaSize, bucketOffsets);
for(Index i = n; i >= 1; i --) {
Index j = sa[i] - 1;
if(j >= 0 && types[j]) sa[-- bucketOffsets[(int)str[j]]] = j;
}
}
template<typename AlphaT>
void SuffixArray::countAlphabets(const AlphaT *str, Index n, int AlphaSize, std::vector<Index> &bucketOffsets, bool b) {
if(b || (int)bucketOffsets.size() / 2 >= AlphaSize) {
std::vector<Index>::iterator alphabetCounts =
b ? bucketOffsets.begin() : bucketOffsets.begin() + AlphaSize;
std::fill(alphabetCounts, alphabetCounts + AlphaSize, 0);
for(Index i = 0; i < n; i ++)
alphabetCounts[(int)str[i]] ++;
}
}
template<typename AlphaT>
void SuffixArray::getBucketOffsets(const AlphaT *str, Index n, bool dir, int AlphaSize, std::vector<Index> &bucketOffsets) {
std::vector<Index>::iterator alphabetCounts;
if((int)bucketOffsets.size() / 2 < AlphaSize) {
countAlphabets(str, n, AlphaSize, bucketOffsets, true);
alphabetCounts = bucketOffsets.begin();
} else alphabetCounts = bucketOffsets.begin() + AlphaSize;
Index cumsum = 1;
if(dir) {
for(int i = 0; i < AlphaSize; i ++) {
cumsum += alphabetCounts[i];
bucketOffsets[i] = cumsum;
}
} else {
for(int i = 0; i < AlphaSize; i ++) {
Index x = alphabetCounts[i];
bucketOffsets[i] = cumsum;
cumsum += x;
}
}
}
void SuffixArray::buildInverseSuffixArray() {
Index n = length();
inverseSuffixArray.resize(n + 1);
for(Index i = 0; i <= n; i ++)
inverseSuffixArray[suffixArray[i]] = i;
}
void SuffixArray::computeLCPArray(const Alpha *str) {
int n = length();
lcpArray.resize(n + 2);
Index h = 0;
for(Index i = 0; i < n; i ++) {
Index pos = inverseSuffixArray[i];
Index j = suffixArray[pos - 1];
Index hbound = std::min(n - j, n - i);
for(Index k = 0; h < hbound && str[i + h] == str[j + h]; ++ h);
lcpArray[pos - 1] = h;
if(h > 0) -- h;
}
lcpArray[n] = lcpArray[n + 1] = 0;
}
SuffixArray::Index SuffixArray::computeLCP(Index i, Index j) const {
Index n = length();
if(i == j) return n - i;
Index x = inverseSuffixArray[i], y = inverseSuffixArray[j];
if(x > y) std::swap(x, y);
return lcpArrayRMQ.queryVal(&lcpArray[0], x, y - 1);
}
unsigned xor128() {
static unsigned x = 123456789, y = 362436069, z = 521288629, w = 88675123;
unsigned t = x ^ (x << 11);
x = y; y = z; z = w;
return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}
struct Node {
static vector<Node> buf;
static size_t bufp;
typedef const Node *Ref;
Ref left, right;
int size;
int key;
Node() : left(NULL), right(NULL), size(1), key(0) {}
static Ref newNode(Ref left, Ref right, int key) {
if(bufp == buf.size()) {
cerr << "Memory exhausted!" << endl;
abort();
}
Node *p = new(&buf[bufp ++])Node;
p->left = left, p->right = right, p->key = key;
return p;
}
inline Ref propagated() const {
return this;
}
inline Ref linkl(Ref c) const {
return newNode(c, right, key);
}
inline Ref linkr(Ref c) const {
return newNode(left, c, key);
}
inline Ref linklr(Ref l, Ref r) const {
return newNode(l, r, key);
}
};
vector<Node> Node::buf;
size_t Node::bufp = 0;
struct RBST {
typedef const Node *Ref;
static int size(Ref t) { return !t ? 0 : t->size; }
typedef pair<Ref, Ref> RefPair;
static RefPair splitKey(Ref t, int key) {
if(!t) return RefPair((Ref)NULL, (Ref)NULL);
t = t->propagated();
if(key <= t->key) {
RefPair p = splitKey(t->left, key);
return RefPair(p.first, t->linkl(p.second));
} else {
RefPair p = splitKey(t->right, key);
return RefPair(t->linkr(p.first), p.second);
}
}
static Ref insertKey(Ref t, Ref n) {
if(!t) return n->linklr(NULL, NULL);
if(xor128() % (t->size + 1) == 0) {
RefPair p = splitKey(t, n->key);
return n->linklr(p.first, p.second);
}
t = t->propagated();
if(n->key <= t->key)
return t->linkl(insertKey(t->left, n));
else
return t->linkr(insertKey(t->right, n));
}
static Ref last(Ref t) {
if(!t || !t->right) return t;
return last(t->right);
};
static Ref head(Ref t) {
if(!t || !t->left) return t;
return head(t->left);
};
};
int main() {
typedef Node::Ref Ref;
Node::buf.resize(10000000);
int T;
scanf("%d", &T);
for(int ii = 0; ii < T; ++ ii) {
Node::bufp = 0;
int N; int A; int B;
scanf("%d%d%d", &N, &A, &B);
string S;
cin >> S;
SuffixArray sa;
sa.buildAll(S.c_str(), N);
vector<Ref> sets(N + 1);
vector<vector<int> > events(N + 1);
multiset<int> curMin;
vector<int> dp(N + 1, INF);
dp[0] = 0;
rer(i, 0, N) {
if(!curMin.empty())
amin(dp[i], *curMin.begin());
for(int t : events[i])
curMin.erase(curMin.find(t));
if(i == N) break;
int x = dp[i];
amin(dp[i + 1], x + A);
int key = sa.inverseSuffixArray[i];
int l = 0, u = i;
while(u - l > 0) {
int mid = (l + u + 1) / 2;
Ref t = sets[i - mid + 1];
bool ok = false;
auto p = RBST::splitKey(t, key);
if(p.first != nullptr) {
int pos = RBST::last(p.first)->key;
ok |= sa.computeLCP(i, sa.suffixArray[pos]) >= mid;
}
if(p.second != nullptr) {
int pos = RBST::head(p.second)->key;
ok |= sa.computeLCP(i, sa.suffixArray[pos]) >= mid;
}
if(ok)
l = mid;
else
u = mid - 1;
}
// cerr << i << ": " << l << endl;
if(l > 0) {
curMin.insert(x + B);
events[i + l].push_back(x + B);
}
sets[i + 1] = RBST::insertKey(sets[i], Node::newNode(0, 0, key));
}
int ans = dp[N];
printf("%d\n", ans);
}
return 0;
}
Java Build a String HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;
import java.util.List;
public class EE {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
for(int T = ni();T > 0;T--){
int n = ni(), a = ni(), b = ni();
char[] s = ns().toCharArray();
SuffixAutomatonOfBit sa = SuffixAutomatonOfBit.build(s);
sa.sortTopologically();
int[] fo = sa.enumFirstOccurrences();
SuffixAutomatonOfBit.Node cur = sa.t0;
int[] reach = new int[n];
int j = 0;
for(int i = 0;i < n;i++){
j = Math.max(i, j);
while(cur != sa.t0 && j-i < cur.link.len+1){
cur = cur.link;
}
while(j < n){
char c = s[j];
SuffixAutomatonOfBit.Node nex = cur.getNext(c);
if(nex == null || fo[nex.id] > i){
break;
}
cur = nex;
j++;
}
reach[i] = j;
}
long[] dp = new long[n+1];
Arrays.fill(dp, Long.MAX_VALUE / 2);
dp[0] = 0;
SegmentTreeRMQL st = new SegmentTreeRMQL(dp);
int pre = 0;
for(int i = 1;i <= n;i++){
while(pre < n && reach[pre] < i)pre++;
dp[i] = Math.min(dp[i-1] + a, st.min(pre, i) + b);
st.update(i, dp[i]);
}
out.println(dp[n]);
}
}
public static class SegmentTreeRMQL {
public int M, H, N;
public long[] st;
public SegmentTreeRMQL(int n)
{
N = n;
M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
H = M>>>1;
st = new long[M];
Arrays.fill(st, 0, M, Long.MAX_VALUE);
}
public SegmentTreeRMQL(long[] a)
{
N = a.length;
M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
H = M>>>1;
st = new long[M];
for(int i = 0;i < N;i++){
st[H+i] = a[i];
}
Arrays.fill(st, H+N, M, Long.MAX_VALUE);
for(int i = H-1;i >= 1;i--)propagate(i);
}
public void update(int pos, long x)
{
st[H+pos] = x;
for(int i = (H+pos)>>>1;i >= 1;i >>>= 1)propagate(i);
}
private void propagate(int i)
{
st[i] = Math.min(st[2*i], st[2*i+1]);
}
public long minx(int l, int r){
if(l >= r)return 0L;
long min = Long.MAX_VALUE;
while(l != 0){
int f = l&-l;
if(l+f > r)break;
long v = st[(H+l)/f];
if(v < min)min = v;
l += f;
}
while(l < r){
int f = r&-r;
long v = st[(H+r)/f-1];
if(v < min)min = v;
r -= f;
}
return min;
}
public long min(int l, int r){ return l >= r ? Long.MAX_VALUE / 3 : min(l, r, 0, H, 1);}
private long min(int l, int r, int cl, int cr, int cur)
{
if(l <= cl && cr <= r){
return st[cur];
}else{
int mid = cl+cr>>>1;
long ret = Long.MAX_VALUE;
if(cl < r && l < mid){
ret = Math.min(ret, min(l, r, cl, mid, 2*cur));
}
if(mid < r && l < cr){
ret = Math.min(ret, min(l, r, mid, cr, 2*cur+1));
}
return ret;
}
}
public int firstle(int l, long v) {
int cur = H+l;
while(true){
if(st[cur] <= v){
if(cur < H){
cur = 2*cur;
}else{
return cur-H;
}
}else{
cur++;
if((cur&cur-1) == 0)return -1;
if((cur&1)==0)cur>>>=1;
}
}
}
public int lastle(int l, long v) {
int cur = H+l;
while(true){
if(st[cur] <= v){
if(cur < H){
cur = 2*cur+1;
}else{
return cur-H;
}
}else{
if((cur&cur-1) == 0)return -1;
cur--;
if((cur&1)==1)cur>>>=1;
}
}
}
}
public static class SuffixAutomatonOfBit {
public Node t0;
public int len;
public Node[] nodes;
public int gen;
private SuffixAutomatonOfBit(int n)
{
gen = 0;
nodes = new Node[2*n];
this.t0 = makeNode(0, null);
}
private Node makeNode(int len, Node original)
{
Node node = new Node();
node.id = gen;
node.original = original;
node.len = len;
nodes[gen++] = node;
return node;
}
public static class Node
{
public int id;
public int len;
public char key;
public Node link;
private Node[] next = new Node[3];
public Node original;
public int np = 0;
public int hit = 0;
public void putNext(char c, Node to)
{
to.key = c;
if(hit<<~(c-'a')<0){
for(int i = 0;i < np;i++){
if(next[i].key == c){
next[i] = to;
return;
}
}
}
hit |= 1<<c-'a';
if(np == next.length){
next = Arrays.copyOf(next, np*2);
}
next[np++] = to;
}
public boolean containsKeyNext(char c)
{
return hit<<~(c-'a')<0;
// for(int i = 0;i < np;i++){
// if(next[i].key == c)return true;
// }
// return false;
}
public Node getNext(char c)
{
if(hit<<~(c-'a')<0){
for(int i = 0;i < np;i++){
if(next[i].key == c)return next[i];
}
}
return null;
}
public List<String> suffixes(char[] s)
{
List<String> list = new ArrayList<String>();
if(id == 0)return list;
int first = original != null ? original.len : len;
for(int i = link.len + 1;i <= len;i++){
list.add(new String(s, first - i, i));
}
return list;
}
}
public static SuffixAutomatonOfBit build(char[] str)
{
int n = str.length;
SuffixAutomatonOfBit sa = new SuffixAutomatonOfBit(n);
sa.len = str.length;
Node last = sa.t0;
for(char c : str){
last = sa.extend(last, c);
}
return sa;
}
public Node extend(Node last, char c)
{
Node cur = makeNode(last.len+1, null);
Node p;
for(p = last; p != null && !p.containsKeyNext(c);p = p.link){
p.putNext(c, cur);
}
if(p == null){
cur.link = t0;
}else{
Node q = p.getNext(c); // not null
if(p.len + 1 == q.len){
cur.link = q;
}else{
Node clone = makeNode(p.len+1, q);
clone.next = Arrays.copyOf(q.next, q.next.length);
clone.hit = q.hit;
clone.np = q.np;
clone.link = q.link;
for(;p != null && q.equals(p.getNext(c)); p = p.link){
p.putNext(c, clone);
}
q.link = cur.link = clone;
}
}
return cur;
}
public SuffixAutomatonOfBit lexSort()
{
for(int i = 0;i < gen;i++){
Node node = nodes[i];
Arrays.sort(node.next, 0, node.np, new Comparator<Node>() {
public int compare(Node a, Node b) {
return a.key - b.key;
}
});
}
return this;
}
public SuffixAutomatonOfBit sortTopologically()
{
int[] indeg = new int[gen];
for(int i = 0;i < gen;i++){
for(int j = 0;j < nodes[i].np;j++){
indeg[nodes[i].next[j].id]++;
}
}
Node[] sorted = new Node[gen];
sorted[0] = t0;
int p = 1;
for(int i = 0;i < gen;i++){
Node cur = sorted[i];
for(int j = 0;j < cur.np;j++){
if(--indeg[cur.next[j].id] == 0){
sorted[p++] = cur.next[j];
}
}
}
for(int i = 0;i < gen;i++)sorted[i].id = i;
nodes = sorted;
return this;
}
public int[] enumFirstOccurrences()
{
int[] fo = new int[gen];
for(int i = gen-1;i >= 0;i--){
fo[i] = nodes[i].original == null ? nodes[i].len : fo[nodes[i].original.id];
}
return fo;
}
public int[] enumLastOccurrences()
{
int[] lo = new int[gen];
for(int i = gen-1;i >= 0;i--){
lo[i] = Math.max(lo[i], nodes[i].len);
lo[nodes[i].link.id] = Math.max(lo[nodes[i].link.id], lo[i]);
}
return lo;
}
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new EE().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
Python 3 Build a String HackerRank Solution
rep = int(input())
for r in range(rep):
l, a, b = map(int, input().split(' '))
s = input().strip()
i = 1
cost = 0
cost = [float('inf')] * (l + 1)
cost[0] = 0
k = 0
while i <= l: # i is the number of char finished, s[i-1] finished
# find the maximun substring
j = max(i, k)
while j<=l and (s[i-1:j] in s[:i-1]):
j += 1
# s[i-1:j-1] in s
if j-1 != i:
cost[j-1] = min(cost[i-1] + b, cost[j-1])
k = j
cost[i] = min(cost[i-1] + a, cost[i])
#print(cost)
#print(s[i], a)
i += 1
print(cost[-1])
Python 2 Build a String HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
def sol():
N, A, B = map(int, raw_input().strip().split())
S = raw_input().strip()
res = [0]*N
res[0] = A
maxl = 0
for i in range(1,N):
minv = res[i-1] + A
cp, idx, newl = False, i, 0
for k in range(maxl,-1,-1):
if S[i-k:i+1] in S[0:i-k]:
cp, idx, newl = True, i-k, k+1
break
if cp: minv = min(minv, res[idx-1]+B)
maxl = newl
res[i] = minv
print res[-1]
T = int(raw_input().strip())
for x in range(T):
sol()
C Build a String HackerRank Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
char s[30001];
int sublens[30001] = { 0 };
void longestsubstr(int pos) {
int i, max = 0;
for (i = 0; i < pos; i++) {
if (s[i] != s[pos]) sublens[i] = 0;
else {
sublens[i] = sublens[i+1] + 1;
if (i + sublens[i] > pos) sublens[i] = pos - i;
if (sublens[i] > max) max = sublens[i];
}
}
sublens[pos] = max;
}
int main() {
int t, t1;
scanf("%d", &t);
for (t1 = 0; t1 < t; t1++) {
int n, a, b, sublen, i, j, temp;
scanf("%d %d %d", &n, &a, &b);
scanf("%s", s);
int ar[30001];
for (i = 0; i < n; i++) {
ar[i] = 0x7FFFFFFF;
sublens[i] = 0;
}
for (i = n - 1; i >= 1; i--) longestsubstr(i);
ar[0] = a;
for (i = 1; i < n; i++) {
if (ar[i-1] + a < ar[i]) ar[i] = ar[i-1] + a;
sublen = sublens[i];
temp = ar[i-1] + b;
for (j = 0; j < sublen; j++) if (temp < ar[i+j]) ar[i+j] = temp;
}
printf("%d\n", ar[n-1]);
}
return 0;
}
Comments 1