HackerRank Two Strings Game problem solution

Posted on By YASH PAL

In this HackerRank Two Strings Game problem solution there are two strings A and B. Initially, some strings A’ and B’ are written on the sheet of paper. A’ is always a substring of A and B’ is always a substring of B. A move consists of appending a letter to exactly one of these strings: either to A’ or to B’. After the move, the constraint of A’ being a substring of A and B’ is a substring of B should still be satisfied. Players take their moves alternately. We call a pair (A’, B’) a position.

Two players are playing this game optimally. That means that if a player has a move that leads to his/her victory, he/she will definitely use this move. If a player is unable to make a move, he loses.

Alice and Bob are playing this game. Alice makes the first move. As always, she wants to win and this time she does a clever trick. She wants the starting position to be the Kth lexicographically winning position for the first player (i.e. her). Consider two positions (A’1, B’1) and (A’2, B’2). We consider the first position lexicographically smaller than the second if A1 is lexicographically smaller than A2, or if A1 is equal to A2 and B1 is lexicographically smaller than B2.

Please help her to find such a position, knowing the strings A, B, and the integer K.

HackerRank Two Strings Game problem solution

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

  static final int maxn = 300000;
  static final long limit = 1000000000000000000l;

  static boolean[] was = new boolean[30];
  static long[] srt;

  static class Sfa {

    long[] dp;
    long[] grundySum;
    long[] ways;

    int[][] next;
    int[] len;
    int[] lnk;
    int[] grundy;

    int nodes, last;

    Sfa(int n) {
      dp = new long[maxn * 2 + 3];
      grundySum = new long[30];
      ways = new long[maxn * 2 + 3];

      next = new int[26][maxn * 2 + 3];
      len = new int[maxn * 2 + 3];
      lnk = new int[maxn * 2 + 3];
      grundy = new int[maxn * 2 + 3];

      nodes = last = 1;
      len[1] = lnk[1] = 0;
    }

    void push(int c) {
      int cur = ++nodes, p;
      len[cur] = len[last] + 1;
      for (p = last; (p > 0) && (next[c][p] == 0); p = lnk[p]) {
        next[c][p] = cur;
      }
      if (p == 0) {
        lnk[cur] = 1;
      } else {
        int q = next[c][p];
        if (len[p] + 1 == len[q]) {
          lnk[cur] = q;
        } else {
          int clone = ++nodes;
          len[clone] = len[p] + 1;
          for (int j = 0; j < 26; j++) {
            next[j][clone] = next[j][q];
          }
          lnk[clone] = lnk[q];
          for (; (p > 0) && next[c][p] == q; p = lnk[p]) {
            next[c][p] = clone;
          }
          lnk[q] = lnk[cur] = clone;
        }
      }
      last = cur;
    }

    void grundyPrecalc() {
      for (int i = 1; i <= nodes; i++) {
        srt[i] = ((long)len[i]  << 32l) | i;
      }
      Arrays.sort(srt, 1, nodes + 1);
      for (int i = 1; i <= nodes; i++) {
        int k = (int)(srt[nodes - i + 1] & 0xffffffffL);
        dp[k] = 1;
        Arrays.fill(was, false);
        for (int j = 0; j < 26; j++) {
          if (next[j][k] > 0) {
            was[grundy[next[j][k]]] = true;
          }
        }
        for (int j = 0; j < 30; j++) {
          if (!was[j]) {
            grundy[k] = j;
            break;
          }
        }
      }
    }

    void substrPrecalc() {
      for (int i = 1; i <= nodes; i++) {
        srt[i] = ((long)len[i]  << 32l) | i;
      }
      Arrays.sort(srt, 1, nodes + 1);
      for (int i = 1; i <= nodes; i++) {
        int k = (int)(srt[nodes - i + 1] & 0xffffffffL);
        dp[k] = 1;
        for (int j = 0; j < 26; j++) {
          if (next[j][k] > 0) {
            dp[k] += dp[next[j][k]];
          }
        }
      }
      ways[1] = 1;
      for (int i = 1; i <= nodes; i++) {
        int k = (int)(srt[i] & 0xffffffffL);
        for (int j = 0; j < 26; j++) {
          if (next[j][k] > 0) {
            ways[next[j][k]] += ways[k];
          }
        }
      }
      for (int i = 1; i <= nodes; i++) {
        grundySum[grundy[i]] += ways[i];
      }
    }

    void dpRecalc(int badValue) {
      for (int i = 1; i <= nodes; i++) {
        srt[i] = ((long)len[i]  << 32l) | i;
      }
      Arrays.sort(srt, 1, nodes + 1);
      for (int i = 1; i <= nodes; i++) {
        int k = (int)(srt[nodes - i + 1] & 0xffffffffL);
        dp[k] = grundy[k] != badValue ? 1 : 0;
        for (int j = 0; j < 26; j++) {
          if (next[j][k] > 0) {
            dp[k] += dp[next[j][k]];
          }
        }
      }
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    long k = Long.parseLong(st.nextToken());

    srt = new long[maxn * 2 + 3];

    Sfa sfa1 = new Sfa(n);

    char[] a = br.readLine().toCharArray();
    for (int i = 0; i < n; i++) {
      sfa1.push(a[i] - 'a');
    }

    Sfa sfa2 = new Sfa(n);

    char[] b = br.readLine().toCharArray();
    for (int i = 0; i < m; i++) {
      sfa2.push(b[i] - 'a');
    }

    sfa1.grundyPrecalc();
    for (int i = 1; i <= (sfa2.nodes > 29 ? 29 : sfa2.nodes); i++) {
      was[i] = false;
    }

    sfa2.grundyPrecalc();
    sfa2.substrPrecalc();

    for (int i = 1; i <= sfa1.nodes; i++) {
      srt[i] = ((long)sfa1.len[i]  << 32l) | i;
    }
    Arrays.sort(srt, 1, sfa1.nodes + 1);
    for (int i = 1; i <= sfa1.nodes; i++) {
      int kk = (int)(srt[sfa1.nodes - i + 1] & 0xffffffffL);
      sfa1.dp[kk] = sfa2.dp[1] - sfa2.grundySum[sfa1.grundy[kk]];
      for (int j = 0; j < 26; j++) {
        if (sfa1.next[j][kk] > 0) {
          sfa1.dp[kk] += sfa1.dp[sfa1.next[j][kk]];
          if (sfa1.dp[kk] > limit) {
            sfa1.dp[kk] = limit;
          }
        }
      }
    }

    if (k > sfa1.dp[1]) {
      bw.write("no solution");
      bw.newLine();

      bw.close();
      br.close();
      return;
    }
    int cur = 1;
    while (k > 0) {
      if (k <= sfa2.dp[1] - sfa2.grundySum[sfa1.grundy[cur]]) {
        break;
      } else {
        k -= sfa2.dp[1] - sfa2.grundySum[sfa1.grundy[cur]];
      }
      for (int j = 0; j < 26; j++)
        if (k > sfa1.dp[sfa1.next[j][cur]])
          k -= sfa1.dp[sfa1.next[j][cur]];
        else {
          bw.write('a' + j);
          cur = sfa1.next[j][cur];
          break;
        }
    }
    bw.newLine();

    int badValue = sfa1.grundy[cur];
    sfa2.dpRecalc(badValue);
    cur = 1;
    while (k > 0) {
      if (sfa2.grundy[cur] != badValue) {
        --k;
        if (k == 0) {
          break;
        }
      }
      for (int j = 0; j < 26; j++) {
        if (k > sfa2.dp[sfa2.next[j][cur]]) {
          k -= sfa2.dp[sfa2.next[j][cur]];
        } else {
          bw.write('a' + j);
          cur = sfa2.next[j][cur];
          break;
        }
      }
    }

    bw.newLine();

    bw.close();
    br.close();
  }
}

{“mode”:”full”,”isActive”:false}

Problem solution in C++.

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
 
#define maxn 300000
#define limit 1000000000000000000LL
 
long long k;
 
int n, m, i, j, cur, bad_value, kk;
char a[maxn], b[maxn];
bool was[30];
pair<int, int> srt[maxn * 2 + 3];
 
struct sfa {
 
	long long dp[maxn * 2 + 3], grundy_sum[30], ways[maxn * 2 + 3];
 
	int next[maxn * 2 + 3][26], len[maxn * 2 + 3], lnk[maxn * 2 + 3], grundy[maxn * 2 + 3];
	int nodes, last, j;
 
	void init () {
		nodes = last = 1;
		len[1] = lnk[1] = 0;
	}
 
	void push (int c) {
		int cur = ++nodes, p;
		len[cur] = len[last] + 1;
		for(p = last; p && !next[p][c]; p = lnk[p]) next[p][c] = cur;
		if (!p) lnk[cur] = 1; else {
			int q = next[p][c];
			if (len[p] + 1 == len[q]) lnk[cur] = q; else {
				int clone = ++nodes;
				len[clone] = len[p] + 1;
				for(int j = 0; j < 26; j++) next[clone][j] = next[q][j];
				lnk[clone] = lnk[q];
				for(; p && next[p][c] == q; p = lnk[p]) next[p][c] = clone;
				lnk[q] = lnk[cur] = clone;
			}
		}
		last = cur;
	}
 
	void grundy_precalc () {
		for(i = 1; i <= nodes; i++) srt[i] = make_pair(len[i], i);
		sort(srt + 1, srt + nodes + 1);
		for(i = 1; i <= nodes; i++) {
			int k = srt[nodes - i + 1].second;
			dp[k] = 1;
			for(j = 0; j < 30; j++) was[j] = 0;
			for(j = 0; j < 26; j++) if (next[k][j]) was[grundy[next[k][j]]] = true;
			for(j = 0; j < 30; j++) if (!was[j]) {
				grundy[k] = j;
				break;
			}
		}		
	}	
 
	void substr_precalc () {
		for(i = 1; i <= nodes; i++) srt[i] = make_pair(len[i], i);
		sort(srt + 1, srt + nodes + 1);
		for(i = 1; i <= nodes; i++) {
			int k = srt[nodes - i + 1].second;
			dp[k] = 1;
			for(j = 0; j < 26; j++) if (next[k][j]) dp[k] += dp[next[k][j]];
		}
		ways[1] = 1;
		for(i = 1; i <= nodes; i++) for(j = 0; j < 26; j++) if (next[srt[i].second][j]) ways[next[srt[i].second][j]] += ways[srt[i].second];
		for(i = 1; i <= nodes; i++) grundy_sum[grundy[i]] += ways[i];
	}
 
	void dp_recalc (int bad_value) {
		for(i = 1; i <= nodes; i++) srt[i] = make_pair(len[i], i);
		sort(srt + 1, srt + nodes + 1);
		for(i = 1; i <= nodes; i++) {
			int k = srt[nodes - i + 1].second;
			dp[k] = grundy[k] != bad_value;
			for(j = 0; j < 26; j++) if (next[k][j]) dp[k] += dp[next[k][j]];
		}
	}
 
} sfa1, sfa2;
 
int main (int argc, char * const argv[]) {
//	freopen("input.txt", "r", stdin);
	scanf("%d %d %lldn", &n, &m, &k);
 
	sfa1.init();
	sfa2.init();
 
	for(i = 0; i < n; i++) {
		a[i] = getchar();
		while (a[i] < 'a' || a[i] > 'z') a[i] = getchar();
		sfa1.push(a[i] - 'a');
	}
	for(i = 0; i < m; i++) {
		b[i] = getchar();
		while (b[i] < 'a' || b[i] > 'z') b[i] = getchar();
		sfa2.push(b[i] - 'a');
	}
 
	sfa1.grundy_precalc();
	for(i = 1; i <= sfa2.nodes; i++) was[i] = false;
	sfa2.grundy_precalc();
 
	sfa2.substr_precalc();	
 
	for(i = 1; i <= sfa1.nodes; i++) srt[i] = make_pair(sfa1.len[i], i);
	sort(srt + 1, srt + sfa1.nodes + 1);
	for(i = 1; i <= sfa1.nodes; i++) {
		kk = srt[sfa1.nodes - i + 1].second;
		sfa1.dp[kk] = sfa2.dp[1] - sfa2.grundy_sum[sfa1.grundy[kk]];
		for(j = 0; j < 26; j++) if (sfa1.next[kk][j]) {
			sfa1.dp[kk] += sfa1.dp[sfa1.next[kk][j]];
			if (sfa1.dp[kk] > limit) sfa1.dp[kk] = limit;
		}
	}		
 
	if (k > sfa1.dp[1]) {
		puts("no solution");
		return 0;
	}
 
	cur = 1;
	while (k > 0) {
		if (k <= sfa2.dp[1] - sfa2.grundy_sum[sfa1.grundy[cur]]) break; else k -= sfa2.dp[1] - sfa2.grundy_sum[sfa1.grundy[cur]];
		for(j = 0; j < 26; j++) if (k > sfa1.dp[sfa1.next[cur][j]]) k -= sfa1.dp[sfa1.next[cur][j]]; else {
			putchar('a' + j);
			cur = sfa1.next[cur][j];
			break;
		}
	}
	puts("");	
 
	sfa2.dp_recalc(bad_value = sfa1.grundy[cur]);
	cur = 1;
	while (k > 0) {
		if (sfa2.grundy[cur] != bad_value) {
			--k;
			if (k == 0) break;
		}
		for(j = 0; j < 26; j++) if (k > sfa2.dp[sfa2.next[cur][j]]) k -= sfa2.dp[sfa2.next[cur][j]]; else {
			putchar('a' + j);
			cur = sfa2.next[cur][j];
			break;
		}
	}
	puts("");
    return 0;
}

{“mode”:”full”,”isActive”:false}

Problem solution in C.

#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 solutionn");
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("%sn",ans);
val=0;
K-=KK;
return;
}
if(KK+total-dp[root->x]>=K){
ans[idx]=0;
printf("%sn",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("%sn",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("%sn",ans);
return;
}
if(val!=root->x && KK+1==K){
ans[idx]=0;
printf("%sn",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("%sn",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;
}

{“mode”:”full”,”isActive”:false}

algorithm, coding problems

Related Tutorials

HackerRank pointers in c problem solution HackerRank Pointers in C solution c
Ruby tutorial hello hackerrank problem solution Ruby Tutorial – Hello HackerRank! problem solution coding problems
HackerRank Summing Pieces problem solution algorithm