Table of Contents
Two Strings Game – 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++ Two Strings Game HackerRank Solution
#include <iostream>
#include <ctime>
#include <fstream>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <utility>
#include <cctype>
#include <list>
using namespace std;
#define FORALL(i,a,b) for(int i=(a);i<=(b);++i)
#define FOR(i,n) for(int i=0;i<(n);++i)
#define FORB(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<int,int> pii;
typedef map<int,int> mii;
#define pb push_back
#define mp make_pair
#define INF 1000000000000001000ll
#define MAXG 27
#define MAXN 600010
#define NO_ASSERT
#ifndef REGULAR_ASSERT
#ifndef NO_ASSERT
#undef assert
#define assert sassert
#else
#undef assert
#define assert(x)
#endif
#endif
void sassert(bool x) {
if (!x) { cout << "assertion failed!" << endl; exit(0); }
}
void add(ll& a, ll b) {
if (a >= INF-b) a=INF;
else a+=b;
}
void mul(ll& a, ll b) {
if (b==0) a=0;
else if (a >= (INF+b-1)/b) a = INF;
else a *= b;
}
struct my_map {
int s[26];
my_map() { memset(s,-1,sizeof(s)); }
int count(int idx) { return s[idx-'a'] >= 0; }
void clear() { memset(s,-1,sizeof(s)); }
int& operator[](int idx) {
idx -= 'a';
if (s[idx] < 0) s[idx] = 0;
return s[idx];
}
};
// a Suffix-Automaton data structure over a string S
// It is "the smallest DFA which accepts all suffixes of S".
// Fast linear time construction (constant is like 5 at worst).
// based on http://e-maxx.ru/algo/suffix_automata. Originally by Blumer et al
// Code under the Public DomainS
struct state {
// Modified for the present problem (Two Strings Game, HackerRank 20/20 Feb 2014 )
// Includes grundy numbers (i.e.: the nim-sum)
// Turns out, the nim-sums work nicely for Suffix Automata! (each state is a node)
int len, link, grundy;
ll paths[MAXG]; // the # of paths from this state downward to any node with grundy g
my_map next;
state(int a, int b) {
len=a; link=b; next.clear();
grundy = 0; memset(paths,0,sizeof(paths));
}
state() { len=link=0; next.clear(); memset(paths,0,sizeof(paths)); }
};
// add next (alphabetic) character c to the dfa Q (an array of states).
// K is the number of states. tail is the state representing the entire string
void sa_add(char c, state* Q, int& K, int& tail) {
assert(K<MAXN - 5);
int x,y, cur = K++;
Q[cur].len = Q[tail].len+1; Q[cur].link = -1;
for(x=tail; x>=0 && !Q[x].next.count(c); x = Q[x].link)
Q[x].next[c] = cur;
if (x<0) Q[cur].link = 0;
else {
y = Q[x].next[c];
if (Q[y].len == Q[x].len + 1) {
Q[cur].link = y;
} else {
int cl = K++; // clone
Q[cl].len = Q[x].len+1; Q[cl].link = Q[y].link;//state(Q[x].len + 1, Q[y].link);
Q[cl].next = Q[y].next;
for(; x>=0 && Q[x].next[c]==y; x=Q[x].link)
Q[x].next[c] = cl;
Q[y].link = Q[cur].link = cl;
}
}
tail = cur;
}
#define MAXL 300002
bool vis[MAXN];
bool mex[MAXN][MAXG]; // a temporary array to store reachable grundy numbers (and to find the mex)
void dfs(int i, state* Q) {
assert(i<MAXN && i>=0);
//if (vis[i]) return;
//vis[i] = true;
//cout << i << endl;
FOR(g,MAXG) mex[i][g] = 0, Q[i].paths[g] = 0;
FORALL(c,'a','z') if (Q[i].next.count(c)) {
int j = Q[i].next[c];
//assert(vis[j]);
//dfs(j,Q);
mex[i][Q[j].grundy] = true;
}
Q[i].grundy = -1;
FOR(g,MAXG) {
if (!mex[i][g]) {
Q[i].grundy = g;
break;
}
}
assert(Q[i].grundy >= 0);
FORALL(c,'a','z') if (Q[i].next.count(c)) {
int j = Q[i].next[c];
FOR(g,MAXG) {
add(Q[i].paths[g], Q[j].paths[g]);
}
}
add(Q[i].paths[Q[i].grundy],1);
assert(Q[i].grundy <= 26);
}
// construct the suffix automaton for the string t
// store the resulting states into the array Q;
// return the number of states. Will be no more than 2|t| + 2 (ish?)
int sa_construct(char* t, state* Q) {
int n = strlen(t), first[n+1], next[2*n-1], K = 1, tail = 0;
Q[0].len = 0; Q[0].link = -1; Q[0].next.clear();
FOR(i,n) sa_add(t[i],Q,K,tail);
// do a dfs / dp to compute grundy numbers (nim-sums)
// also compute all paths that lead to each grundy number starting from any node
//memset(vis,0,sizeof(vis));
FORALL(i,0,n) first[i] = -1;
FOR(i,K) next[i] = first[Q[i].len], first[Q[i].len] = i;
FORB(k,n,0) for(int i = first[k]; i>=0; i = next[i])
dfs(i,Q);
//Q[Q[i].link].occs += Q[i].occs;
//FORB(i,K-1,0) dfs(i,Q);
return K;
}
// Uses for suffix automata (treat it exactly like a trie)
// All of these run in O(|p|) time!!!!
// find pattern p in the search text (i.e.: suffix automaton Q)
// return true if p is found in the string
bool sa_find(state* Q, char* p) {
for(int s=0; *p && Q[s].next.count(*p); s = Q[s].next[*p], p++);
return ((*p) == 0); // reached end of string with no errors! we found it
}
// find a pattern p and return its grundy number.
// return -1 if not found
int sa_grundy(state* Q, const char* p) {
int s;
for(s=0; *p && Q[s].next.count(*p); s = Q[s].next[*p], p++);
return (((*p)==0)?Q[s].grundy:-1);
}
state Qa[MAXN], Qb[MAXN];
char A[MAXL], B[MAXL];
char a[MAXL], b[MAXL];
// number of paths in b (starting from state s) that
// lead to a grundy number not equal to <grun>
//ll Q0P[MAXG];
inline ll get_winning(int grun, state* Q, int s=0) {
ll ans = 0;
FOR(g,MAXG) if (g != grun){
//if (s == 0) add(ans,Q0P[g]);
/*else*/
add(ans,Q[s].paths[g]);
}
return ans;
}
int main () {
int N,M;
ll K;
cin >> N >> M >> K;
//FOR(i,N) A[i] = 'a'+(i%2);
//FOR(i,N) B[i] = 'b'+(i%2);
//FOR(i,N) A[i] = 'a';
//FOR(j,M) B[j] = 'b';
//A[N-1] = 'b';
//B[N-1] = 'a';
scanf("%s%s",A,B);
//N = strlen(A);
//M = strlen(B);
sa_construct(A,Qa);
sa_construct(B,Qb);
//FOR(g,MAXG) Q0P[g] = Qa[0].paths[g];
//assert(Kb < MAXN);
//assert(Ka < MAXN);
//int Kb = sa_construct(B,Qb);
//assert(Ka < MAXN && Kb < MAXN);
//cout << sizeof(Qa) << " " << Ka << endl;
//return 0;
ll total_winning = 0;
FOR(g,MAXG) {
ll tmp = Qa[0].paths[g];
mul(tmp,get_winning(g,Qb));
add(total_winning, tmp);
}
if (total_winning < K) {
cout << "no solution" << endl;
return 0;
}
// we can now assume there is a solution
// first construct a
ll num_winning, total_here, tmp, x;
int len = 0;
int s = 0, news; // current state in the suffix automaton
while(K) {
// check the empty case
num_winning = get_winning(Qa[s].grundy,Qb);
if (num_winning >= K) break;
// otherwise, need to add another character
// note: we keep the old "num_winning" (counting the number of possibilities we've skipped)
//bool found = false;
FORALL(c,'a','z') {
if (!Qa[s].next.count(c)) continue;
news = Qa[s].next[c];
total_here = 0;
FOR(g,MAXG) {
tmp = Qa[news].paths[g];
mul(tmp,get_winning(g,Qb));
add(total_here, tmp);
}
x = num_winning; add(x,total_here);
if (x >= K) {
K -= num_winning;
a[len++] = c;
//found = true;
s = news;
break;
} else {
num_winning += total_here;
}
}
// eventually it will find something (since we assumed there is a solution)
//assert(found);
}
// now construct b
int a_grundy = Qa[s].grundy;
//sa_construct(B,Qa);
len = 0;
s = 0; // current state in the suffix automaton
while(K) {
// check the empty case
num_winning = ((Qb[s].grundy == a_grundy)?0:1);
if (num_winning >= K) { K -= 1; break; }
// now we push a new character to b
// note: we keep the old "num_winning" (counting the number of possibilities we've skipped)
//bool found = false;
FORALL(c,'a','z') {
if (!Qb[s].next.count(c)) continue;
news = Qb[s].next[c];
tmp = get_winning(a_grundy, Qb, news);
if (num_winning + tmp >= K) {
K -= num_winning;
b[len++] = c;
// found = true;
s = news;
break;
} else {
num_winning += tmp;
}
}
// eventually it will find something (since we assumed there is a solution
//assert(found);
}
assert(!K);
printf("%s\n%s\n",a,b);
//cout << a << endl;
//cout << b << endl;
}
Java Two Strings Game HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;
public class Solution {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
// static String INPUT = "2 2 5 ab cd";
// static String INPUT = "5 2 4 aabaa cd";
// static String INPUT = "4 2 4 aaab bb";
static class Result
{
int[] sa;
int[] lcp;
int[][] branches;
long[] count;
int[] zero, one;
int[] deadline;
public Result(int[] sa, int[] lcp, int[][] branches, long[] count,
int[] zero, int[] one, int[] deadline) {
this.sa = sa;
this.lcp = lcp;
this.branches = branches;
this.count = count;
this.zero = zero;
this.one = one;
this.deadline = deadline;
}
}
static void solve()
{
int n = ni(), m = ni();
long K = nl();
char[] a = ns(n);
char[] b = ns(m);
Result ra = go(a);
Result rb = go(b);
long[] ca = ra.count;
long[] cb = rb.count;
if(cb.length < ca.length){
cb = Arrays.copyOf(cb, ca.length);
}
long totcb = 0;
for(long v : cb)totcb += v;
Arrays.sort(ra.branches, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[0] - b[0];
}
});
K--;
// ""
{
long lcount = totcb - cb[ra.branches[0][3]];
if(K < lcount){
int[] resb = kth(rb, K, ra.branches[0][3]);
out.println("");
out.println(new String(b, resb[0], resb[1]));
return;
}else{
K -= lcount;
}
}
int bp = 0;
bp++;
for(int i = 0;i < n;i++){
// row
long lcount = 0;
lcount += ra.zero[i] * (totcb - cb[0]);
lcount += ra.one[i] * (totcb - cb[1]);
int obp = bp;
while(bp < ra.branches.length && ra.branches[bp][0] == i){
lcount += totcb - cb[ra.branches[bp][3]];
bp++;
}
if(K < lcount){
// letter
int[] row = new int[n-ra.sa[i]];
Arrays.fill(row, -1);
for(int j = obp;j < bp;j++){
row[ra.branches[j][2]-1] = ra.branches[j][3];
}
for(int j = n-ra.sa[i]-1;j >= ra.deadline[i]+1;j--){
if(row[j] == -1){
if(j == n-ra.sa[i]-1){
row[j] = 0;
}else{
row[j] = row[j+1] > 0 ? 0 : 1;
}
}
}
// tr("row", row);
for(int j = ra.deadline[i]+1;j < n-ra.sa[i];j++){
long llcount = totcb - cb[row[j]];
if(K < llcount){
// rb
int[] resa = new int[]{ra.sa[i], j+1};
int[] resb = kth(rb, K, row[j]);
out.println(new String(a, resa[0], resa[1]));
out.println(new String(b, resb[0], resb[1]));
return;
}else{
K -= llcount;
}
}
}else{
K -= lcount;
}
}
out.println("no solution");
}
static int[] kth(Result rb, long K, int proh)
{
Arrays.sort(rb.branches, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[0] - b[0];
}
});
// ""
if(rb.branches[0][3] != proh){
if(K == 0){
return new int[]{0, 0};
}else{
K--;
}
}
int n = rb.sa.length;
int bp = 1;
for(int i = 0;i < n;i++){
// row
long lcount = 0;
if(proh != 0)lcount += rb.zero[i];
if(proh != 1)lcount += rb.one[i];
int obp = bp;
while(bp < rb.branches.length && rb.branches[bp][0] == i){
if(proh != rb.branches[bp][3])lcount++;
bp++;
}
if(K < lcount){
// letter
int[] row = new int[n-rb.sa[i]];
Arrays.fill(row, -1);
for(int j = obp;j < bp;j++){
row[rb.branches[j][2]-1] = rb.branches[j][3];
}
for(int j = n-rb.sa[i]-1;j >= rb.deadline[i]+1;j--){
if(row[j] == -1){
if(j == n-rb.sa[i]-1){
row[j] = 0;
}else{
row[j] = row[j+1] > 0 ? 0 : 1;
}
}
}
for(int j = rb.deadline[i]+1;j < n-rb.sa[i];j++){
if(row[j] != proh){
if(K == 0){
return new int[]{rb.sa[i], j+1};
}
K--;
}
}
}else{
K -= lcount;
}
}
return null;
}
static Result go(char[] a)
{
int[] sa = suffixsort(a);
int[] lcp = buildLCP(a, sa);
int[][] branches = findBranches(lcp);
LResult lres = countNimber(sa, lcp, branches);
return new Result(sa, lcp, branches, lres.count, lres.zero, lres.one, lres.deadline);
}
private static LResult countNimber(int[] sa, int[] lcp, int[][] branches)
{
int n = sa.length;
int[] zero = new int[n];
int[] one = new int[n];
int[] deadline = new int[n];
Arrays.fill(deadline, -1);
// nimber???suffix???????
int[] hs = new int[n];
int[] nim = new int[n];
Arrays.fill(nim, -1);
long[] count = new long[n+1];
for(int i = 0;i < n;i++){
hs[i] = n-sa[i]+1;
}
int[] alive = new int[n];
Arrays.fill(alive, 1);
int[] ftalive = buildFenwick(alive);
int bp = 0;
int[] bs2 = new int[n];
for(int[] branch : branches){
int sp = 0;
int L = branch[0];
int R = branch[1];
int h = branch[2];
if(L == -1)L = 0;
int bs = 0;
// 2$
// .1$
// ..010
// .010$
// 010
for(int i = L;i <= R && i >= 0;i = after(ftalive, i)){
if(nim[i] >= 0)count[nim[i]]++;
int bet = hs[i]-h-1;
if(nim[i] == 0){
count[0] += bet / 2;
count[1] += (bet+1)/2;
zero[i] += bet/2;
one[i] += (bet+1)/2;
// 0|10|1
bs |= 1<<(bet&1);
}else{
count[0] += (bet+1) / 2;
count[1] += bet/2;
zero[i] += (bet+1)/2;
one[i] += bet/2;
if(bet == 0){
if(nim[i] >= 0){
if(nim[i] <= 31){
bs |= 1<<nim[i];
}else{
bs2[sp++] = nim[i];
}
}
}else{
bs |= 1<<((bet&1)^1);
}
}
hs[i] = h;
if(i > L){
// kill
alive[i] = 0;
deadline[i] = h-1;
addFenwick(ftalive, i, -1);
}
}
int clus = Integer.numberOfTrailingZeros(~bs);
if(clus >= 32){
Arrays.sort(bs2, 0, sp);
clus = 32;
for(int q = 0;q < sp;){
if(bs2[q] == clus){
while(q < sp && bs2[q] == clus)q++;
clus++;
}else{
break;
}
}
}
branches[bp++][3] = nim[L] = clus;
if(branch[0] == -1)count[nim[L]]++;
}
return new LResult(count, zero, one, deadline);
}
static class LResult
{
long[] count;
int[] zero, one;
int[] deadline;
public LResult(long[] count, int[] zero, int[] one, int[] deadline) {
this.count = count;
this.zero = zero;
this.one = one;
this.deadline = deadline;
}
}
static int[][] findBranches(int[] a)
{
int n = a.length;
long[] ap = new long[n];
for(int i = 0;i < n;i++)ap[i] = (long)(1000000-a[i])<<32|i;
Arrays.sort(ap);
int[][] branches = new int[n][];
// aabaa
// a$
// aa$
// aabaa$
// abaa$
// baa
int p = 0;
int[] flag = new int[n];
Arrays.fill(flag, 1);
int[] ft = buildFenwick(flag);
for(int i = 0;i < n;i++){
int j;
int last = (int)ap[i];
int va = 1000000-(int)(ap[i]>>>32);
for(j = (int)ap[i];j >= 0 && j < n && flag[j] == 1 && a[j] >= va;j = after(ft, j)){ // on index
last = j;
flag[j] = 0;
addFenwick(ft, j, -1);
}
// tr(restoreFenwick(ft));
// tr(flag);
// tr(j,i);
if(j == (int)ap[i])continue;
// if(j == ap[i][1])continue; // already processed
branches[p++] = new int[]{before(ft, (int)ap[i]), last, va, -1};
// branches[p++] = new int[]{before(ft, ap[i][1]), last, ap[i][0], -1};
}
return Arrays.copyOf(branches, p);
}
public static int sumFenwick(int[] ft, int i)
{
int sum = 0;
for(i++;i > 0;i -= i&-i)sum += ft[i];
return sum;
}
public static void addFenwick(int[] ft, int i, int v)
{
if(v == 0)return;
int n = ft.length;
for(i++;i < n;i += i&-i)ft[i] += v;
}
public static int findGFenwick(int[] ft, int v)
{
int i = 0;
int n = ft.length;
for(int b = Integer.highestOneBit(n);b != 0 && i < n;b >>= 1){
if(i + b < n){
int t = i + b;
if(v >= ft[t]){
i = t;
v -= ft[t];
}
}
}
return v != 0 ? -(i+1) : i-1;
}
public static int valFenwick(int[] ft, int i)
{
return sumFenwick(ft, i) - sumFenwick(ft, i-1);
}
public static int[] restoreFenwick(int[] ft)
{
int n = ft.length-1;
int[] ret = new int[n];
for(int i = 0;i < n;i++)ret[i] = sumFenwick(ft, i);
for(int i = n-1;i >= 1;i--)ret[i] -= ret[i-1];
return ret;
}
public static int before(int[] ft, int x)
{
int u = sumFenwick(ft, x-1);
if(u == 0)return -1;
return findGFenwick(ft, u-1)+1;
}
public static int after(int[] ft, int x)
{
int u = sumFenwick(ft, x);
int f = findGFenwick(ft, u);
if(f+1 >= ft.length-1)return -1;
return f+1;
}
public static int[] buildFenwick(int[] a)
{
int n = a.length;
int[] ft = new int[n+1];
System.arraycopy(a, 0, ft, 1, n);
for(int k = 2, h = 1;k <= n;k*=2, h*=2){
for(int i = k;i <= n;i+=k){
ft[i] += ft[i-h];
}
}
return ft;
}
public static int[] buildLCP(char[] str, int[] sa)
{
int n = str.length;
int h = 0;
int[] lcp = new int[n];
int[] b = new int[n];
for(int i = 0;i < n;i++)b[sa[i]] = i;
for(int i = 0;i < n;i++){
if(b[i] > 0){
for(int j = sa[b[i]-1]; j+h<n && i+h<n && str[j+h] == str[i+h]; h++);
lcp[b[i]] = h;
}else{
lcp[b[i]] = 0;
}
if(h > 0)h--;
}
return lcp;
}
private static interface BaseArray {
public int get(int i);
public void set(int i, int val);
public int update(int i, int val);
}
private static class CharArray implements BaseArray {
private char[] m_A = null;
private int m_pos = 0;
CharArray(char[] A, int pos) {
m_A = A;
m_pos = pos;
}
public int get(int i) {
return m_A[m_pos + i] & 0xffff;
}
public void set(int i, int val) {
m_A[m_pos + i] = (char) (val & 0xffff);
}
public int update(int i, int val) {
return m_A[m_pos + i] += val & 0xffff;
}
}
private static class IntArray implements BaseArray {
private int[] m_A = null;
private int m_pos = 0;
IntArray(int[] A, int pos) {
m_A = A;
m_pos = pos;
}
public int get(int i) {
return m_A[m_pos + i];
}
public void set(int i, int val) {
m_A[m_pos + i] = val;
}
public int update(int i, int val) {
return m_A[m_pos + i] += val;
}
}
/* find the start or end of each bucket */
private static void getCounts(BaseArray T, BaseArray C, int n, int k) {
int i;
for(i = 0;i < k;++i){
C.set(i, 0);
}
for(i = 0;i < n;++i){
C.update(T.get(i), 1);
}
}
private static void getBuckets(BaseArray C, BaseArray B, int k, boolean end) {
int i, sum = 0;
if(end != false){
for(i = 0;i < k;++i){
sum += C.get(i);
B.set(i, sum);
}
}else{
for(i = 0;i < k;++i){
sum += C.get(i);
B.set(i, sum - C.get(i));
}
}
}
/* sort all type LMS suffixes */
private static void LMSsort(BaseArray T, int[] SA, BaseArray C,
BaseArray B, int n, int k) {
int b, i, j;
int c0, c1;
/* compute SAl */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, false); /* find starts of buckets */
j = n - 1;
b = B.get(c1 = T.get(j));
--j;
SA[b++] = (T.get(j) < c1) ? ~j : j;
for(i = 0;i < n;++i){
if(0 < (j = SA[i])){
if((c0 = T.get(j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
--j;
SA[b++] = (T.get(j) < c1) ? ~j : j;
SA[i] = 0;
}else if(j < 0){
SA[i] = ~j;
}
}
/* compute SAs */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, true); /* find ends of buckets */
for(i = n - 1, b = B.get(c1 = 0);0 <= i;--i){
if(0 < (j = SA[i])){
if((c0 = T.get(j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
--j;
SA[--b] = (T.get(j) > c1) ? ~(j + 1) : j;
SA[i] = 0;
}
}
}
private static int LMSpostproc(BaseArray T, int[] SA, int n, int m) {
int i, j, p, q, plen, qlen, name;
int c0, c1;
boolean diff;
/*
* compact all the sorted substrings into the first m items of SA 2*m
* must be not larger than n (proveable)
*/
for(i = 0;(p = SA[i]) < 0;++i){
SA[i] = ~p;
}
if(i < m){
for(j = i, ++i;;++i){
if((p = SA[i]) < 0){
SA[j++] = ~p;
SA[i] = 0;
if(j == m){
break;
}
}
}
}
/* store the length of all substrings */
i = n - 1;
j = n - 1;
c0 = T.get(n - 1);
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
for(;0 <= i;){
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
if(0 <= i){
SA[m + ((i + 1) >> 1)] = j - i;
j = i + 1;
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
}
}
/* find the lexicographic names of all substrings */
for(i = 0, name = 0, q = n, qlen = 0;i < m;++i){
p = SA[i];
plen = SA[m + (p >> 1)];
diff = true;
if((plen == qlen) && ((q + plen) < n)){
for(j = 0;(j < plen) && (T.get(p + j) == T.get(q + j));++j){
}
if(j == plen){
diff = false;
}
}
if(diff != false){
++name;
q = p;
qlen = plen;
}
SA[m + (p >> 1)] = name;
}
return name;
}
/* compute SA and BWT */
private static void induceSA(BaseArray T, int[] SA, BaseArray C,
BaseArray B, int n, int k) {
int b, i, j;
int c0, c1;
/* compute SAl */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, false); /* find starts of buckets */
j = n - 1;
b = B.get(c1 = T.get(j));
SA[b++] = ((0 < j) && (T.get(j - 1) < c1)) ? ~j : j;
for(i = 0;i < n;++i){
j = SA[i];
SA[i] = ~j;
if(0 < j){
if((c0 = T.get(--j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
SA[b++] = ((0 < j) && (T.get(j - 1) < c1)) ? ~j : j;
}
}
/* compute SAs */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, true); /* find ends of buckets */
for(i = n - 1, b = B.get(c1 = 0);0 <= i;--i){
if(0 < (j = SA[i])){
if((c0 = T.get(--j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
SA[--b] = ((j == 0) || (T.get(j - 1) > c1)) ? ~j : j;
}else{
SA[i] = ~j;
}
}
}
/*
* find the suffix array SA of T[0..n-1] in {0..k-1}^n use a working space
* (excluding T and SA) of at most 2n+O(1) for a constant alphabet
*/
private static void SA_IS(BaseArray T, int[] SA, int fs, int n, int k) {
BaseArray C, B, RA;
int i, j, b, m, p, q, name, newfs;
int c0, c1;
int flags = 0;
if(k <= 256){
C = new IntArray(new int[k], 0);
if(k <= fs){
B = new IntArray(SA, n + fs - k);
flags = 1;
}else{
B = new IntArray(new int[k], 0);
flags = 3;
}
}else if(k <= fs){
C = new IntArray(SA, n + fs - k);
if(k <= (fs - k)){
B = new IntArray(SA, n + fs - k * 2);
flags = 0;
}else if(k <= 1024){
B = new IntArray(new int[k], 0);
flags = 2;
}else{
B = C;
flags = 8;
}
}else{
C = B = new IntArray(new int[k], 0);
flags = 4 | 8;
}
/*
* stage 1: reduce the problem by at least 1/2 sort all the
* LMS-substrings
*/
getCounts(T, C, n, k);
getBuckets(C, B, k, true); /* find ends of buckets */
for(i = 0;i < n;++i){
SA[i] = 0;
}
b = -1;
i = n - 1;
j = n;
m = 0;
c0 = T.get(n - 1);
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
for(;0 <= i;){
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
if(0 <= i){
if(0 <= b){
SA[b] = j;
}
b = B.update(c1, -1);
j = i;
++m;
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
}
}
if(1 < m){
LMSsort(T, SA, C, B, n, k);
name = LMSpostproc(T, SA, n, m);
}else if(m == 1){
SA[b] = j + 1;
name = 1;
}else{
name = 0;
}
/*
* stage 2: solve the reduced problem recurse if names are not yet
* unique
*/
if(name < m){
if((flags & 4) != 0){
C = null;
B = null;
}
if((flags & 2) != 0){
B = null;
}
newfs = (n + fs) - (m * 2);
if((flags & (1 | 4 | 8)) == 0){
if((k + name) <= newfs){
newfs -= k;
}else{
flags |= 8;
}
}
for(i = m + (n >> 1) - 1, j = m * 2 + newfs - 1;m <= i;--i){
if(SA[i] != 0){
SA[j--] = SA[i] - 1;
}
}
RA = new IntArray(SA, m + newfs);
SA_IS(RA, SA, newfs, m, name);
RA = null;
i = n - 1;
j = m * 2 - 1;
c0 = T.get(n - 1);
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
for(;0 <= i;){
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
if(0 <= i){
SA[j--] = i + 1;
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
}
}
for(i = 0;i < m;++i){
SA[i] = SA[m + SA[i]];
}
if((flags & 4) != 0){
C = B = new IntArray(new int[k], 0);
}
if((flags & 2) != 0){
B = new IntArray(new int[k], 0);
}
}
/* stage 3: induce the result for the original problem */
if((flags & 8) != 0){
getCounts(T, C, n, k);
}
/* put all left-most S characters into their buckets */
if(1 < m){
getBuckets(C, B, k, true); /* find ends of buckets */
i = m - 1;
j = n;
p = SA[m - 1];
c1 = T.get(p);
do{
q = B.get(c0 = c1);
while (q < j){
SA[--j] = 0;
}
do{
SA[--j] = p;
if(--i < 0){
break;
}
p = SA[i];
}while ((c1 = T.get(p)) == c0);
}while (0 <= i);
while (0 < j){
SA[--j] = 0;
}
}
induceSA(T, SA, C, B, n, k);
C = null;
B = null;
}
/* char */
public static int[] suffixsort(char[] T) {
if(T == null)return null;
int n = T.length;
int[] SA = new int[n];
if(n <= 1){
if(n == 1){
SA[0] = 0;
}
return SA;
}
SA_IS(new CharArray(T, 0), SA, 0, n, 65536);
return SA;
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static 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 static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static 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 static 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 static 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 static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static 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 static 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) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
C Two Strings Game HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define A_SIZE 26
#define MIN_C 'a'
typedef struct _st_node st_node;
typedef struct _st_edge st_edge;
struct _st_node{
int x;
unsigned long long count;
st_node *suffix_link;
st_edge *edges[A_SIZE+1];
};
struct _st_edge{
int from;
int to;
int suffix_index;
st_node *node;
};
int dfs0(st_node *root,int flag);
unsigned long long dfs1(st_node *root);
void dfs2(int idx,st_node *root);
unsigned long long dfs3(st_node *root);
void dfs4(int idx,st_node *root);
void suffix_tree(st_node *root,char *str,int len);
char a[300001],b[300001],ans[300001];
unsigned long long dp[50],total,K,KK,val;
int main(){
int N,M,i;
st_node r1,r2;
scanf("%d%d%lld%s%s",&N,&M,&K,a,b);
suffix_tree(&r1,a,N);
suffix_tree(&r2,b,M);
dfs0(&r1,0);
dfs0(&r2,1);
for(i=0;i<50;i++)
total+=dp[i];
dfs1(&r1);
if(r1.count<K){
printf("no solution\n");
return 0;
}
dfs2(0,&r1);
dfs3(&r2);
KK=0;
dfs4(0,&r2);
return 0;
}
int dfs0(st_node *root,int flag){
char arr[20];
int len,ret,i;
if(!root){
if(flag)
dp[0]++;
return 0;
}
memset(arr,0,sizeof(arr));
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
len=root->edges[i]->to-root->edges[i]->from+1;
ret=dfs0(root->edges[i]->node,flag);
if(len==1)
arr[ret]=1;
else
if(ret){
if(flag){
dp[0]+=len/2;
dp[1]+=(len-1)/2;
}
if(len%2)
arr[1]=1;
else
arr[0]=1;
}
else{
if(flag){
dp[1]+=len/2;
dp[0]+=(len-1)/2;
}
if(len%2)
arr[0]=1;
else
arr[1]=1;
}
}
for(i=0;i<20 && arr[i];i++);
if(flag)
dp[i]++;
root->x=i;
return i;
}
unsigned long long dfs1(st_node *root){
int len,ret,i;
unsigned long long ret2,count=0;
if(!root)
return total-dp[0];
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
len=root->edges[i]->to-root->edges[i]->from+1;
ret2=dfs1(root->edges[i]->node);
if(root->edges[i]->node)
ret=root->edges[i]->node->x;
else
ret=0;
count+=ret2;
if(ret){
count+=len/2*(total-dp[0]);
count+=(len-1)/2*(total-dp[1]);
}
else{
count+=len/2*(total-dp[1]);
count+=(len-1)/2*(total-dp[0]);
}
}
count+=total-dp[root->x];
root->count=count;
return count;
}
void dfs2(int idx,st_node *root){
int len,ret,start,i,j;
unsigned long long t1,t2;
if(!root){
ans[idx]=0;
printf("%s\n",ans);
val=0;
K-=KK;
return;
}
if(KK+total-dp[root->x]>=K){
ans[idx]=0;
printf("%s\n",ans);
val=root->x;
K-=KK;
return;
}
KK+=total-dp[root->x];
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
len=root->edges[i]->to-root->edges[i]->from+1;
if(root->edges[i]->node){
ret=root->edges[i]->node->x;
t2=root->edges[i]->node->count;
}
else{
ret=0;
t2=total-dp[0];
}
t1=0;
if(ret){
t1+=len/2*(total-dp[0]);
t1+=(len-1)/2*(total-dp[1]);
}
else{
t1+=len/2*(total-dp[1]);
t1+=(len-1)/2*(total-dp[0]);
}
if(KK+t1+t2<K)
KK+=t1+t2;
else if(KK+t1<K){
KK+=t1;
for(j=root->edges[i]->from;j<=root->edges[i]->to;j++)
ans[idx+j-root->edges[i]->from]=a[j];
dfs2(idx+root->edges[i]->to-root->edges[i]->from+1,root->edges[i]->node);
return;
}
else{
if((ret && len%2) || (!ret && len%2==0))
start=1;
else
start=0;
for(j=root->edges[i]->from;j<root->edges[i]->to;j++,start^=1){
ans[idx+j-root->edges[i]->from]=a[j];
if(KK+total-dp[start]>=K){
ans[idx+j+1-root->edges[i]->from]=0;
printf("%s\n",ans);
val=start;
K-=KK;
return;
}
KK+=total-dp[start];
}
return;
}
}
return;
}
unsigned long long dfs3(st_node *root){
int len,ret,i;
unsigned long long ret2,count=0;
if(!root){
if(val)
return 1;
return 0;
}
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
len=root->edges[i]->to-root->edges[i]->from+1;
ret2=dfs3(root->edges[i]->node);
if(root->edges[i]->node)
ret=root->edges[i]->node->x;
else
ret=0;
count+=ret2;
if(ret){
if(val!=0)
count+=len/2;
if(val!=1)
count+=(len-1)/2;
}
else{
if(val!=1)
count+=len/2;
if(val!=0)
count+=(len-1)/2;
}
}
if(val!=root->x)
count++;
root->count=count;
return count;
}
void dfs4(int idx,st_node *root){
int len,ret,start,i,j;
unsigned long long t1,t2;
if(!root){
ans[idx]=0;
printf("%s\n",ans);
return;
}
if(val!=root->x && KK+1==K){
ans[idx]=0;
printf("%s\n",ans);
return;
}
if(val!=root->x)
KK++;
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
len=root->edges[i]->to-root->edges[i]->from+1;
if(root->edges[i]->node){
ret=root->edges[i]->node->x;
t2=root->edges[i]->node->count;
}
else{
ret=0;
if(val)
t2=1;
else
t2=0;
}
t1=0;
if(ret){
if(val!=0)
t1+=len/2;
if(val!=1)
t1+=(len-1)/2;
}
else{
if(val!=1)
t1+=len/2;
if(val!=0)
t1+=(len-1)/2;
}
if(KK+t1+t2<K)
KK+=t1+t2;
else if(KK+t1<K){
KK+=t1;
for(j=root->edges[i]->from;j<=root->edges[i]->to;j++)
ans[idx+j-root->edges[i]->from]=b[j];
dfs4(idx+root->edges[i]->to-root->edges[i]->from+1,root->edges[i]->node);
return;
}
else{
if((ret && len%2) || (!ret && len%2==0))
start=1;
else
start=0;
for(j=root->edges[i]->from;j<root->edges[i]->to;j++,start^=1){
ans[idx+j-root->edges[i]->from]=b[j];
if(val!=start){
if(KK+1==K){
ans[idx+j+1-root->edges[i]->from]=0;
printf("%s\n",ans);
return;
}
KK++;
}
}
return;
}
}
return;
}
void suffix_tree(st_node *root,char *str,int len){
int a_edge,a_len=0,remainder=0,need_insert,from,i;
st_node *a_node=root,*pre_node,*t_node;
st_edge *t_edge;
memset(root,0,sizeof(st_node));
for(i=0;i<len;i++){
need_insert=0;
pre_node=NULL;
remainder++;
if(i==len)
need_insert=1;
else if(a_len)
if(str[a_node->edges[a_edge]->from+a_len]==str[i])
if(a_node->edges[a_edge]->from+a_len==a_node->edges[a_edge]->to){
a_node=a_node->edges[a_edge]->node;
a_len=0;
}
else
a_len++;
else
need_insert=1;
else
if(a_node->edges[str[i]-MIN_C])
if(a_node->edges[str[i]-MIN_C]->from==a_node->edges[str[i]-MIN_C]->to)
a_node=a_node->edges[str[i]-MIN_C]->node;
else{
a_edge=str[i]-MIN_C;
a_len=1;
}
else
need_insert=1;
if(need_insert)
for(;remainder>0;remainder--){
if(!a_len)
if(i==len){
a_node->edges[A_SIZE]=(st_edge*)malloc(sizeof(st_edge));
a_node->edges[A_SIZE]->suffix_index=i-remainder+1;
a_node->edges[A_SIZE]->node=NULL;
}
else{
if(a_node->edges[str[i]-MIN_C]){
if(pre_node)
pre_node->suffix_link=a_node;
if(a_node->edges[str[i]-MIN_C]->from==a_node->edges[str[i]-MIN_C]->to)
a_node=a_node->edges[str[i]-MIN_C]->node;
else{
a_edge=str[i]-MIN_C;
a_len=1;
}
break;
}
t_edge=(st_edge*)malloc(sizeof(st_edge));
t_edge->from=i;
t_edge->to=len-1;
t_edge->suffix_index=i-remainder+1;
t_edge->node=NULL;
a_node->edges[str[i]-MIN_C]=t_edge;
t_node=a_node;
}
else{
if(i!=len && str[a_node->edges[a_edge]->from+a_len]==str[i]){
if(pre_node)
pre_node->suffix_link=a_node;
if(a_node->edges[a_edge]->from+a_len==a_node->edges[a_edge]->to){
a_node=a_node->edges[a_edge]->node;
a_len=0;
}
else
a_len++;
break;
}
t_node=(st_node*)malloc(sizeof(st_node));
memset(t_node,0,sizeof(st_node));
t_edge=(st_edge*)malloc(sizeof(st_edge));
t_edge->from=a_node->edges[a_edge]->from+a_len;
t_edge->to=a_node->edges[a_edge]->to;
t_edge->suffix_index=a_node->edges[a_edge]->suffix_index;
t_edge->node=a_node->edges[a_edge]->node;
from=a_node->edges[a_edge]->from;
a_node->edges[a_edge]->node=t_node;
a_node->edges[a_edge]->to=a_node->edges[a_edge]->from+a_len-1;
t_node->edges[str[t_edge->from]-MIN_C]=t_edge;
if(i==len){
t_node->edges[A_SIZE]=(st_edge*)malloc(sizeof(st_edge));
t_node->edges[A_SIZE]->suffix_index=i-remainder+1;
t_node->edges[A_SIZE]->node=NULL;
}
else{
t_edge=(st_edge*)malloc(sizeof(st_edge));
t_edge->from=i;
t_edge->to=len-1;
t_edge->suffix_index=i-remainder+1;
t_edge->node=NULL;
t_node->edges[str[i]-MIN_C]=t_edge;
}
}
if(pre_node)
pre_node->suffix_link=t_node;
pre_node=t_node;
if(a_node==root && a_len>0){
if(remainder>1)
a_edge=str[i-remainder+2]-MIN_C;
from=i-remainder+2;
a_len--;
}
else if(a_node!=root)
if(a_node->suffix_link)
a_node=a_node->suffix_link;
else
a_node=root;
while(a_len>0 && a_len>=a_node->edges[a_edge]->to-a_node->edges[a_edge]->from+1){
a_len-=a_node->edges[a_edge]->to-a_node->edges[a_edge]->from+1;
from+=a_node->edges[a_edge]->to-a_node->edges[a_edge]->from+1;
a_node=a_node->edges[a_edge]->node;
a_edge=str[from]-MIN_C;
}
}
}
return;
}
Comments 1