Hello Programmers, In this post, you will learn how to solve HackerRank Ashton and String Solution. This problem is a part of the HackerRank Algorithms Series.
One more thing to add, don’t straight away look for the solutions, first try to solve the problems by yourself. If you find any difficulty after trying several times, then look for the solutions. We are going to solve the HackerRank Algorithms problems using C, CPP, JAVA, PYTHON, JavaScript & SCALA Programming Languages.
HackerRank Ashton and String
Task
Ashton appeared for a job interview and is asked the following question. Arrange all the distinct substrings of a given string in lexicographical order and concatenate them. Print the kth character of the concatenated string. It is assured that given value of k will be valid i.e. there will be a kth character. Can you help Ashton out with this?
For example, given the string s = abc, its distinct substrings are [a, ab, abc, abcd, b, bc, bcd, c, cd, d]. Sorted and concatenated, they make the string aababcabcdbbcbcdccdd. If K = 5 then, the answer is b, the 5th character of the 1-indexed concatenated string.
Note We have distinct substrings here, i.e. if string is aa, it’s distinct substrings are a and aa.
Function Description
Complete the ashtonString function in the editor below. It should return the kth character from the concatenated string, 1–based indexing.
ashtonString has the following parameters:
– s: a string
– k: an integer
Input Format
The first line will contain an integer t, the number of test cases.
Each of the subsequent t pairs of lines is as follows:
– The first line of each test case contains a string, s.
– The second line contains an integer, k.
Constraints
- 1 <= t <= 5
- 1 <= |s| <= 105
- Each character of string s ∈ ascii[a – z]
- k will be an appropriate integer.
Output Format
Print the kth character (1–based index) of the concatenation of the ordered distinct substrings of s.
Sample Input
1
dbac
3
Sample Output
c
Explanation
The substrings when arranged in lexicographic order are as follows
a, ac, b, ba, bac, c, d, db, dba, dbac
On concatenating them, we get
aacbbabaccddbdbadbac
The third character in this string is c.
HackerRank Ashton and String Solution
HackerRank Ashton and String Solution in C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define N 100001
void merge(int*a,int*left,int*right,int left_size, int right_size);
void sort_a(int*a,int size);
void suffixSort(int n);
void LCP(int n);
char str[N]; //input
int rank[N], pos[N], lcp[N]; //output
int cnt[N], next[N]; //internal
int bh[N], b2h[N];
int main(){
char cc;
int T,n,i;
long long K,c,t,x,tt;
double xx;
scanf("%d",&T);
while(T--){
scanf("%s%lld",str,&K);
n=strlen(str);
suffixSort(n);
LCP(n);
c=0;
for(i=0;i<n;i++){
tt=c;
c+=(lcp[i]+1+n-pos[i])*(long long)(n-pos[i]-lcp[i])/2;
if(K<=c){
xx=(-1+sqrt(4*(2*(K-tt)+lcp[i]+lcp[i]*(long long)lcp[i])))/2;
x=(long long)xx;
t=K-tt-(lcp[i]+1+x)*(x-lcp[i])/2;
if(!t)
cc=str[pos[i]+x-1];
else
cc=str[pos[i]+t-1];
break;
}
}
printf("%c\n",cc);
}
return 0;
}
void merge(int*a,int*left,int*right,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right[j];
j++;
} else if (j == right_size) {
a[i+j] = left[i];
i++;
} else if (str[left[i]] <= str[right[j]]) {
a[i+j] = left[i];
i++;
} else {
a[i+j] = right[j];
j++;
}
}
return;
}
void sort_a(int*a,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int *left,*right;
left=(int*)malloc(m*sizeof(int));
right=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++)
left[i]=a[i];
for(i=0;i<size-m;i++)
right[i]=a[i+m];
sort_a(left,m);
sort_a(right,size-m);
merge(a,left,right,m,size-m);
free(left);
free(right);
return;
}
void suffixSort(int n){
//sort suffixes according to their first characters
int h,i,j,k;
for (i=0; i<n; ++i){
pos[i] = i;
}
sort_a(pos, n);
//{pos contains the list of suffixes sorted by their first character}
for (i=0; i<n; ++i){
bh[i] = i == 0 || str[pos[i]] != str[pos[i-1]];
b2h[i] = 0;
}
for (h = 1; h < n; h <<= 1){
//{bh[i] == false if the first h characters of pos[i-1] == the first h characters of pos[i]}
int buckets = 0;
for (i=0; i < n; i = j){
j = i + 1;
while (j < n && !bh[j]) j++;
next[i] = j;
buckets++;
}
if (buckets == n) break; // We are done! Lucky bastards!
//{suffixes are separted in buckets containing strings starting with the same h characters}
for (i = 0; i < n; i = next[i]){
cnt[i] = 0;
for (j = i; j < next[i]; ++j){
rank[pos[j]] = i;
}
}
cnt[rank[n - h]]++;
b2h[rank[n - h]] = 1;
for (i = 0; i < n; i = next[i]){
for (j = i; j < next[i]; ++j){
int s = pos[j] - h;
if (s >= 0){
int head = rank[s];
rank[s] = head + cnt[head]++;
b2h[rank[s]] = 1;
}
}
for (j = i; j < next[i]; ++j){
int s = pos[j] - h;
if (s >= 0 && b2h[rank[s]]){
for (k = rank[s]+1; !bh[k] && b2h[k]; k++) b2h[k] = 0;
}
}
}
for (i=0; i<n; ++i){
pos[rank[i]] = i;
bh[i] |= b2h[i];
}
}
for (i=0; i<n; ++i){
rank[pos[i]] = i;
}
}
// End of suffix array algorithm
void LCP(int n){
int l=0,i,j,k;
for(i=0;i<n;i++){
k=rank[i];
if(!k)
continue;
j=pos[k-1];
while(str[i+l]==str[j+l])
l++;
lcp[k]=l;
if(l>0)
l--;
}
lcp[0]=0;
return;
}HackerRank Ashton and String Solution in Cpp
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MAXLEN = (int)1e5 + 5;
char s[MAXLEN];
int SA[MAXLEN], cnt[MAXLEN], ary1[MAXLEN], ary2[MAXLEN];
int *Rank, *Height;
inline bool cmp(int *r, int a, int b, int l) {
return r[a] == r[b] && r[a + l] == r[b + l];
}
void make_suffix_array(int MSIZE, int len) {
int p, *x, *y, *tmp, i, j, k;
x = ary1; y = ary2;
memset(cnt, 0, sizeof(int) * MSIZE);
for (i = 0; i < len; i++) cnt[x[i] = s[i]]++;
for (i = 1; i < MSIZE; i++) cnt[i] += cnt[i - 1];
for (i = len - 1; i >= 0; i--) SA[--cnt[x[i]]] = i;
for (j = p = 1; p < len; j <<= 1, MSIZE = p) {
for (p = 0, i = len - j; i < len; i++) y[p++] = i;
for (i = 0; i < len; i++) {
if (SA[i] >= j) y[p++] = SA[i] - j;
}
memset(cnt, 0, sizeof(int) * MSIZE);
for (i = 0; i < len; i++) cnt[x[y[i]]]++;
for (i = 1; i < MSIZE; i++) cnt[i] += cnt[i - 1];
for (i = len - 1; i >= 0; i--) SA[--cnt[x[y[i]]]] = y[i];
tmp = x; x = y; y = tmp;
x[SA[0]] = 0;
for (i = p = 1; i < len; i++) {
x[SA[i]] = cmp(y, SA[i - 1], SA[i], j) ? p - 1 : p++;
}
}
Rank = x;
Height = y;
for (i = k = 0; i < len - 1; i++) {
if (k > 0) k--;
j = SA[Rank[i] - 1];
while (s[i + k] == s[j + k]) k++;
Height[Rank[i]] = k;
}
}
LL get(LL x,LL y){
return (x+y)*(y-x+1)/2;
}
int main(){
CASET{
RS(s);
int n=LEN(s);
LL K;
cin>>K;
make_suffix_array(128,n+1);
int now=0;
REPP(i,1,n+1){
now=Height[i];
if(K<=get(now+1,n-SA[i])){
LL ll=now+1,rr=n-SA[i];
while(ll<rr){
LL mm=(ll+rr)>>1;
if(get(now+1,mm)<K)ll=mm+1;
else rr=mm;
}
K-=get(now+1,ll-1);
printf("%c\n",s[SA[i]+K-1]);
break;
}
else K-=get(now+1,n-SA[i]);
}
}
return 0;
}HackerRank Ashton and String Solution in Java
import java.io.*;
import java.util.*;
public class Solution {
private static final int mod = (int)1e9+7;
final Random random = new Random(0);
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
for(int t=sc.nextInt();t>0;t--) {
char[] cs = sc.next().toCharArray();
int K = sc.nextInt();
SuffixArray sa = new SuffixArray(cs);
System.out.println(sa.kthDistinctSubstring(K));
}
sc.close();
}
static
public class SuffixArray {
private static final char[] mask = new char[] { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
private static boolean tget(final byte[] t, final int i) { return (t[i>>>3]&mask[i&7]) != 0; }
private static void tset(final byte[] t, final int i, final boolean b) {
if(b) {
t[i>>>3] |= mask[i&7];
} else {
t[i>>>3] &= ~mask[i&7];
}
}
private static boolean isLMS(final byte[] t, final int i) { return i > 0 && tget(t, i) && !tget(t, i-1); }
private static void getBuckets(final Slice s, int[] bkt, int n, int K, boolean end) {
Arrays.fill(bkt, 0);
for(int i = 0; i < n; i++) {
bkt[s.get(i)]++;
}
for(int i = 0, sum = 0; i <= K; i++) {
sum += bkt[i];
bkt[i] = end ? sum : sum - bkt[i];
}
}
private static void induceSAl(final byte[] t, final Slice SA, final Slice s, int[] bkt, int n, int K, boolean end) {
getBuckets(s, bkt, n, K, end);
for(int i = 0; i < n; i++) {
final int j = SA.get(i) - 1;
if(j >= 0 && !tget(t, j)) {
SA.set(bkt[s.get(j)]++, j);
}
}
}
private static void induceSAs(final byte[] t, final Slice SA, final Slice s, int[] bkt, int n, int K, boolean end) {
getBuckets(s, bkt, n, K, end);
for(int i = n - 1; i >= 0; i--) {
final int j = SA.get(i) - 1;
if(j >= 0 && tget(t, j)) {
SA.set(--bkt[s.get(j)], j);
}
}
}
private static void build(final Slice s, final Slice SA, final int n, final int K) {
final byte[] t = new byte[n/8+1];
tset(t, n-2, false);
tset(t, n-1, true);
for(int i = n - 3; i >= 0; i--) {
tset(t, i, s.get(i) < s.get(i+1) || s.get(i) == s.get(i+1) && tget(t, i+1));
}
// stage 1
final int[] bkt = new int[K + 1];
getBuckets(s, bkt, n, K, true);
for(int i = 0; i < n; i++) {
SA.set(i, -1);
}
for(int i = 1; i < n; i++) {
if(isLMS(t, i)) {
SA.set(--bkt[s.get(i)], i);
}
}
induceSAl(t, SA, s, bkt, n, K, false);
induceSAs(t, SA, s, bkt, n, K, true);
int n1 = 0;
for(int i = 0; i < n; i++) {
if(isLMS(t, SA.get(i))) {
SA.set(n1++, SA.get(i));
}
}
for(int i = n1; i < n; i++) {
SA.set(i, -1);
}
int name = 0, prev = -1;
for(int i = 0; i < n1; i++) {
int pos = SA.get(i);
boolean diff = false;
for(int d = 0; d < n; d++) {
if(prev == -1
|| s.get(pos+d) != s.get(prev+d)
|| (tget(t, pos+d) ^ tget(t, prev+d))) {
diff = true;
break;
} else if(d > 0 && (isLMS(t, pos+d) || isLMS(t, prev+d))) {
break;
}
}
if(diff) { name++; prev = pos; }
pos >>>= 1;
SA.set(n1+pos, name - 1);
}
for(int i = n - 1, j = n - 1; i >= n1; i--) {
if(SA.get(i) >= 0) {
SA.set(j--, SA.get(i));
}
}
// stage 2
final Slice SA1 = new Slice(SA, 0);
final Slice s1 = new Slice(SA, n - n1);
if(name < n1) {
build(s1, SA1, n1, name - 1);
} else {
for(int i = 0; i < n1; i++) {
SA1.set(s1.get(i), i);
}
}
// stage 3
// bkt = new int[K + 1];
getBuckets(s, bkt, n, K, true);
for(int i = 1, j = 0; i < n; i++) {
if(isLMS(t, i)) {
s1.set(j++, i);
}
}
for(int i = 0; i < n1; i++) {
SA1.set(i, s1.get(SA1.get(i)));
}
for(int i = n1; i < n; i++) {
SA.set(i, -1);
}
for(int i = n1 - 1, j; i >= 0; i--) {
j = SA.get(i);
SA.set(i, -1);
SA.set(--bkt[s.get(j)], j);
}
induceSAl(t, SA, s, bkt, n, K, false);
induceSAs(t, SA, s, bkt, n, K, true);
}
private static int[] constructSA(final int[] s_, final int n, final int K) {
final Slice s = new Slice(s_, 0);
final Slice SA = new Slice(new int[n], 0);
build(s, SA, n, K);
return SA.ary;
}
private final int n;
private final char[] cs;
public final int[] sa, lcp, rank;
public SuffixArray(final char[] cs) {
this.cs = cs;
int[] input = new int[cs.length + 1];
for(int i = 0; i < cs.length; i++) {
input[i] = cs[i] - 'a' + 1;
}
sa = constructSA(input, input.length, 27);
n = cs.length;
rank = new int[n + 1];
lcp = new int[n];
constructLcp();
}
private void constructLcp() {
for(int i = 0; i <= n; i++) {
rank[sa[i]] = i;
}
int h = 0;
lcp[0] = 0;
for(int i = 0; i < n; i++) {
final int j = sa[rank[i] - 1];
if(h > 0) h--;
for(; j + h < n && i + h < n; h++) {
if(cs[j + h] != cs[i + h]) {
break;
}
}
lcp[rank[i] - 1] = h;
}
}
private static class Slice {
private final int shift;
private final int[] ary;
public int get(final int idx) { return ary[shift + idx]; }
public void set(final int idx, final int val) { ary[shift + idx] = val; }
public Slice(final int[] ary, final int shift) {
this.ary = ary;
this.shift = shift;
}
public Slice(final Slice s, final int shift) {
this.ary = s.ary;
this.shift = s.shift + shift;
}
}
public long numberOfDistinctSubstrings() {
long ret = 0;
for(int i = 1; i <= n; i++) {
ret += n - sa[i] - lcp[i - 1];
}
return ret;
}
public char kthDistinctSubstring(long k) {
for(int i = 1; ; i++) {
for(int j = sa[i] + lcp[i-1]; j < n; j++) {
for(int l = sa[i]; l <= j; l++) {
if(--k == 0) {
return cs[l];
}
}
}
}
}
public static long numberOfDistinctSubstringsNaive(String s) {
Set<String> set = new TreeSet<String>();
for(int i = 0; i < s.length(); i++) {
for(int j = i + 1; j <= s.length(); j++) {
set.add(s.substring(i, j));
}
}
return set.size();
}
public static String kthDistinctSubstringNaive(String s, long k) {
TreeSet<String> set = new TreeSet<String>();
for(int i = 0; i < s.length(); i++) {
for(int j = i + 1; j <= s.length(); j++) {
set.add(s.substring(i, j));
}
}
while(k-- > 0 && !set.isEmpty()) { set.pollFirst(); }
return set.isEmpty() ? " " : set.first();
}
}
}HackerRank Ashton and String Solution in Python
def substring_from_index(string, idx): for i in range(idx + 1, len(string) + 1): yield string[:i] return def substring_from_list(suffixes, k): suffixes.sort() substrs = "" last_suffix = "" for suffix in suffixes: # first, if this is a repeat, skip it if suffix == last_suffix: continue idx = 0 # second, if this is the first value, process the entire thing if last_suffix != "": idx = 1 # first letter will always be the same while idx < len(suffix) and idx < len(last_suffix) and last_suffix[idx] == suffix[idx]: idx = idx + 1 for substr in substring_from_index(suffix, idx): if len(substr) < k: k = k - len(substr) else: return (substr[k], k) last_suffix = suffix return (None, k) ALPHABET = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'] def make_suffix_dict(word): suffix_indexes = dict() for i, ch in enumerate(word): if ch not in suffix_indexes: suffix_indexes[ch] = [i] else: suffix_indexes[ch].append(i) return suffix_indexes def get_suffixes(word, suffix_indexes): suffixes = [word[idx:] for idx in suffix_indexes] return suffixes def find_kth_char(word, k): suffix_indexes = make_suffix_dict(word) for letter in ALPHABET: if letter in suffix_indexes: suffixes = get_suffixes(word, suffix_indexes[letter]) (ch, k) = substring_from_list(suffixes, k) if ch: return ch test_cases = int(input()) for i in range(0, test_cases): line = raw_input() k = int(raw_input()) - 1 print find_kth_char(line, k)
HackerRank Ashton and String Solution using JavaScript
function processData(input) {
input = input.split("\n");
var read = 0;
var tests = input[read++];
for(var test=0; test<tests; test++) {
word = input[read++];
k = input[read++];
run_test_case(word,k);
}
}
function run_test_case(s, k) {
var A = s;
var index = 0;
var object = calculateSuffixArrayLCPAndIntervals(A);
var response = search_character(object.suffix_array, object.intervals, k, A, object.lcp_array);
console.log(response);
}
function findIndex(a, start, end, target) {
var mid;
while (start <= end) {
mid = Math.floor((start + end) / 2);
if (target == a[mid]) {
return mid;
} else if (target < a[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return start;
}
function search_character(suffixes, intervals, k, A, lcp_array) {
var response;
var index = findIndex(intervals, 0, intervals.length - 1, k);
if (index > intervals.length - 1) {
response = "INVALID";
} else {
var begin = intervals[index-1];
var char_pos = k - begin;
var current = A.substring(suffixes[index - 1], A.length);
var lcp = lcp_array[index-1];
var substrings = current.length - lcp;
var string_interval = [0];
for(var i=0; i<substrings; i++) {
string_interval.push(current.length-substrings+i+1 + string_interval[string_interval.length-1]);
}
var char_index = findIndex(string_interval, 0, string_interval.length-1, char_pos);
var current_substring = current.substring(0, current.length-substrings+char_index);
//console.log(current_substring);
//console.log(char_pos);
var current_pos = char_pos - string_interval[char_index-1];
response = current_substring[current_pos-1];
}
return response;
}
///**********
function calculateSuffixArrayLCPAndIntervals(A) {
var MAXLG = 17;
var N = A.length;
var P = [];
P.push([]);
for(var i=0; i<N; i++) {
P[0][i] = A[i].charCodeAt(0) - 'a'.charCodeAt(0);
}
var L = [];
var step = 1;
var count = 1;
var maximum_prefix_size = A.length;
for(step=1,count=1; count >> 1 < maximum_prefix_size; step++, count <<= 1) {
P.push([]);
for(var i=0; i<N; i++) {
var nr0 = P[step-1][i];
var nr1 = i + count < N ? P[step-1][i+count]:-1;
var p = i;
L[i] = { nr0: nr0, nr1: nr1, p:p };
}
L.sort(function(a,b) { return a.nr0==b.nr0 ? ( a.nr1<b.nr1 ? -1 : 1) : (a.nr0 < b.nr0) ? -1 : 1 });
for(var i=0; i<N; i++) {
P[step][L[i].p] = i > 0 && L[i].nr0 == L[i-1].nr0 && L[i].nr1 == L[i-1].nr1 ? P[step][L[i-1].p] : i;
}
}
suffix_array = []
for(var i=0; i<N; i++) {
suffix_array.push( L[i].p );
}
//L has the ordered indexes, create lcp for consecutive pairs with it
var lcp_array = [0]
for(var i=1; i<N; i++) {
lcp_array.push(lcp(L[i-1].p,L[i].p,P,step,N));
}
var intervals = characters_intervals(A, suffix_array,lcp_array);
return { suffix_array: suffix_array, string: A, lcp_array: lcp_array, intervals: intervals }
}
function lcp(x,y,P,step,N) {
var k = 0;
var ret = 0;
if(x==y) return N-x;
for(k=step-1; k>=0 && x<N && y<N; k--)
if(P[k][x] == P[k][y])
x+=1 << k, y+=1 << k, ret += 1 << k;
return ret;
}
function characters_intervals(A, suffix_array, lcp_array) {
var intervals = [ 0 ];
for(var i=0; i<lcp_array.length; i++) {
var size_of_suffix = A.length - suffix_array[i];
var substrings = size_of_suffix - lcp_array[i];
var ap = (substrings-1 > 0) ? ((substrings-1)*(1+(substrings-1)))/2 : 0;
var characters = ( size_of_suffix * substrings ) - ap;
var interval = intervals[intervals.length-1] + characters;
intervals.push(interval);
}
return intervals;
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});HackerRank Ashton and String Solution in Scala
object Solution extends App {
def makeLcpArray(pos: Array[Int], sa: Array[Int], lcp: Array[Int]): Unit = {
val n = sa.length
val rank = Array.ofDim[Int](n)
pos(n) = -1
for (i <- 0 until n) rank(sa(i)) = i
var h = 0
for (i <- 0 until n if rank(i) > 0) {
val j = sa(rank(i) - 1)
while (pos(i + h) == pos(j + h)) h += 1
lcp(rank(i)) = h
if (h > 0) h -= 1
}
}
def createSuffixArray(str: String, sa: Array[Int], LCP: Array[Int]): Unit = {
val n = str.length( );
val s = Array.ofDim[Int](n + 3)
val SA = Array.ofDim[Int](n + 3)
for (i <- 0 until n) {
s(i) = str(i)
}
makeSuffixArray(s, SA, n, 256 )
for (i <- 0 until n) {
sa(i) = SA(i)
}
//println(str)
//println(sa.mkString(", "))
makeLcpArray(s, sa, LCP)
//println(LCP.mkString(", "))
}
def makeSuffixArray(s: Array[Int], sa: Array[Int], n: Int, k: Int): Unit = {
val n0 = (n + 2) / 3
val n1 = (n + 1) / 3
val n2 = n / 3
val t = n0 - n1 // 1 iff n%3 == 1
val n12 = n1 + n2 + t
val s12 = Array.ofDim[Int](n12 + 3)
val SA12 = Array.ofDim[Int](n12 + 3)
val s0 = Array.ofDim[Int](n0)
val SA0 = Array.ofDim[Int](n0)
var j = 0
for (i <- 0 until n + t if i % 3 != 0){
s12(j) = i
j += 1
}
val k12 = assignNames(s, s12, SA12, n0, n12, k)
computeS12(s12, SA12, n12, k12)
computeS0(s, s0, SA0, SA12, n0, n12, k)
merge(s, s12, sa, SA0, SA12, n, n0, n12, t)
}
def assignNames(s: Array[Int], s12: Array[Int], sa12: Array[Int], n0: Int, n12: Int, k: Int): Int = {
radixPass(s12 , sa12, s, 2, n12, k)
radixPass(sa12, s12 , s, 1, n12, k)
radixPass(s12 , sa12, s, 0, n12, k);
var name = 0
var c0 = -1
var c1 = -1
var c2 = -1
for (i <- 0 until n12) {
if (s(sa12(i)) != c0 || s(sa12(i) + 1) != c1 || s(sa12(i) + 2) != c2) {
name += 1
c0 = s(sa12(i))
c1 = s(sa12(i) + 1)
c2 = s(sa12(i) + 2)
}
if(sa12(i) % 3 == 1) s12(sa12(i) / 3) = name;
else s12(sa12(i) / 3 + n0) = name
}
name
}
def radixPass(in: Array[Int], out: Array[Int], s: Array[Int], offset: Int, n: Int, k: Int): Unit = {
val count = Array.ofDim[Int](k + 2)
for (i <- 0 until n) {
count(s(in(i) + offset) + 1) += 1
}
for (i <- 1 to k + 1) {
count(i) += count(i - 1)
}
for (i <- 0 until n) {
out(count(s(in(i) + offset))) = in(i)
count(s(in(i) + offset)) += 1
}
}
def radixPass(in: Array[Int], out: Array[Int], s: Array[Int], n: Int, k: Int): Unit = {
radixPass(in, out, s, 0, n, k)
}
def computeS12(s12: Array[Int], sa12: Array[Int], n12: Int, k12: Int): Unit = {
if (k12 == n12) {
for (i <- 0 until n12) {
sa12(s12(i) - 1) = i
}
} else {
makeSuffixArray(s12, sa12, n12, k12)
for (i <- 0 until n12) {
s12(sa12(i)) = i + 1
}
}
}
def computeS0(s: Array[Int], s0: Array[Int], sa0: Array[Int], sa12: Array[Int], n0: Int, n12: Int, k: Int): Unit = {
var j = 0
for (i <- 0 until n12 if sa12(i) < n0) {
s0(j) = 3 * sa12(i)
j += 1
}
radixPass(s0, sa0, s, n0, k)
}
def merge(s: Array[Int], s12: Array[Int], sa: Array[Int], sa0: Array[Int], sa12: Array[Int], n: Int, n0: Int, n12: Int, u: Int): Unit = {
var p = 0
var k = 0
var t = u
while(t != n12 && p != n0) {
val i = getIndexIntoS(sa12, t, n0)
val j = sa0(p)
if(suffix12IsSmaller(s, s12, sa12, n0, i, j, t )) {
sa(k) = i
k += 1
t += 1
} else {
sa(k) = j
k += 1
p += 1
}
}
while(p < n0) {
sa(k) = sa0(p)
k += 1
p += 1
}
while (t < n12) {
sa(k) = getIndexIntoS(sa12, t, n0)
k += 1
t += 1
}
}
def getIndexIntoS(sa12: Array[Int], t: Int, n0: Int): Int = {
if(sa12(t) < n0)
sa12(t) * 3 + 1;
else
(sa12(t) - n0) * 3 + 2
}
def leq(a1: Int, a2: Int, b1: Int, b2: Int): Boolean = a1 < b1 || a1 == b1 && a2 <= b2
def leq(a1: Int, a2: Int, a3: Int, b1: Int, b2: Int, b3: Int): Boolean = a1 < b1 || a1 == b1 && leq( a2, a3,b2, b3 )
def suffix12IsSmaller(s: Array[Int], s12: Array[Int], sa12: Array[Int], n0: Int, i: Int, j: Int, t: Int): Boolean = {
if( sa12(t) < n0 ) // s1 vs s0; can break tie after 1 character
return leq( s(i), s12(sa12(t) + n0),
s(j), s12(j / 3) );
else // s2 vs s0; can break tie after 2 characters
return leq( s(i), s(i + 1), s12(sa12(t) - n0 + 1),
s(j), s(j + 1), s12(j / 3 + n0) )
}
def solve(s: String, k: Int): Char = {
val len = s.length
val sufarr = Array.ofDim[Int](len)
val LCP = Array.ofDim[Int](len)
createSuffixArray(s, sufarr, LCP);
var reached = 0
var con = ""
for (i <- 0 until sufarr.length if reached < k) {
var j = LCP(i) + 1
while (reached < k && j <= len - sufarr(i)) {
//println(j)
// if (j < len - sufarr(i)) {
// con += s.substring(sufarr(i), sufarr(i) + j)
// }
reached += j
j += 1
}
if (reached >= k) {
//println(con)
//println(reached)
val index = k - (reached - j + 2) + sufarr(i)
//println(index)
return(s(index))
}
}
'd'
}
val cases = readInt
for (i <- 0 until cases) {
val s = readLine
val k = readInt
println(solve(s, k))
}
}HackerRank Ashton and String Solution in Pascal
Disclaimer: This problem (Ashton and String) is generated by HackerRank but the solution is provided by Chase2learn. This tutorial is only for Educational and Learning purposes.
