HackerRank Find Strings problem solution

In this HackerRank Find Strings problem solution, we have given n strings. We need to find out the all substrings of every string and combine all the substrings and sort them. Then we have given an integer to find the element of the 1-indexed lexicographically ordered set of substrings in the set. if there is no element then return INVALID.

Problem solution in Python.

from operator import attrgetter

def lcp(s, t):
    length = min(len(s), len(t))
    for i in range(length):
        if s[i] != t[i]:
            return i
    return length

class Suffix(object):
    def __init__(self, s):
        self.t = s
        self.start = 0
        self.c = -1

    def count(self, s):
        if s:
            self.start = lcp(self.t, s.t)
        self.c = len(self.t) - self.start
        
class SuffixArray(object):
    def __init__(self):
        self.suffixes = []

    def add(self, s):
        for i in range(len(s)):
            self.suffixes.append(Suffix(s[i:]))
    
    def select(self, i):
        for j in range(len(self.suffixes)):
            suffix = self.suffixes[j]
            if suffix.c == -1:
                if j == 0:
                    suffix.count(None)
                else:
                    suffix.count(self.suffixes[j - 1])
            if i <= suffix.c:
                return suffix.t[:suffix.start + i]
            else:
                i = i - suffix.c
        return 'INVALID'

def makeSuffixArray():
    sa = SuffixArray()
    n = int(input())
    for i in range(n):
        w = input()
        sa.add(w)
    sa.suffixes.sort(key = attrgetter('t'))
    return sa

def selectOutput():
    sa = makeSuffixArray()
    q = int(input())
    for i in range(q):
        k = int(input())
        print(sa.select(k))

selectOutput()

Problem solution in Java.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;

public class Solution {
    static TreeSet<String>t;
    public static void main(String[] args) {
        try{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        t=new TreeSet<String>();
        int n=Integer.parseInt(br.readLine());
        for(int i=0;i<n;i++){
        String s=br.readLine();
        for(int j=0;j<s.length();j++){
        t.add(s.substring(j,s.length()));
        }
        }
        Object [] suffix1=(t.toArray());
        String suffix[]=new String[suffix1.length];
        for(int l=0;l<suffix.length;l++){
        suffix[l]=(String)suffix1[l];
        //System.out.println(suffix[l]);
        }
        int len[]=new int[suffix.length];
        int lcp[]=new int[suffix.length];
        len[0]=suffix[0].toString().length();
        lcp[0]=0;
        for(int j=1;j<suffix.length;j++){
        int count=0;
        try{
        while(true){
        if(suffix[j-1].charAt(count)==suffix[j].charAt(count)){
        count++;
        }
        else{
        break;
        }        
        }}catch(StringIndexOutOfBoundsException e){}
        len[j]=suffix[j].length()-count;
        lcp[j]=count;
        }
       int q=Integer.parseInt(br.readLine());
       for(int i=0;i<q;i++){
       int a=Integer.parseInt(br.readLine());
       int a1=0;
       int j=0;
       int count=0;
       try{
       while(j<a){
       a1=j;
       j=j+len[count++];
       }
       count--;
       System.out.println(suffix[count].substring(0, lcp[count]+a-a1));
       }catch(ArrayIndexOutOfBoundsException e){
       System.out.println("INVALID");
       }
       }         
        }catch(IOException e){
        System.out.println(e);        
        }

    }

}

Problem solution in C++.

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <iostream>
#include <vector>
#include <map>
using namespace std;

int const N=510100;
char s[N];                          // N > 256
int n, sa[N], height[N], ranks[N], tmp[N], top[N];
void makesa()                       // O(N * log N)
{
	int i, j, len, na;
	na = (n < 256 ? 256 : n);
	memset(top, 0, na * sizeof(int));
	for (i = 0; i < n ; i++) top[ ranks[i] = s[i] & 0xff ]++;
	for (i = 1; i < na; i++) top[i] += top[i - 1];
	for (i = 0; i < n ; i++) sa[ --top[ ranks[i] ] ] = i;
	for (len = 1; len < n; len <<= 1) {
		for (i = 0; i < n; i++) {
			j = sa[i] - len; if (j < 0) j += n;
			tmp[ top[ ranks[j] ]++ ] = j;
		}
		sa[ tmp[ top[0] = 0 ] ] = j = 0;
		for (i = 1; i < n; i++) {
			if (ranks[ tmp[i] ] != ranks[ tmp[i-1] ] ||
				ranks[ tmp[i]+len ]!=ranks[ tmp[i-1]+len ])
				top[++j] = i;
			sa[ tmp[i] ] = j;
		}
		memcpy(ranks, sa , n * sizeof(int));
		memcpy(sa  , tmp, n * sizeof(int));
		if (j >= n - 1) break;
	}
}
void lcp()                          // O(4 * N)
{
	int i, j, k;
	for (j = ranks[height[i=k=0]=0]; i < n - 1; i++, k++)
		while (k >= 0 && s[i] != s[ sa[j-1] + k ])
			height[j] = (k--), j = ranks[ sa[j] + 1 ];
}

int len[N];
int main()
{
	memset(sa,0,sizeof(sa));
	memset(height,0,sizeof(height));
	memset(len,0,sizeof(len));
	int m,q,i,j,k;
	scanf("%d",&m);
	s[0]=0;
	char str[2010];
	for (i=0,j=0;i<m;i++)
	{
		scanf("%s",str);
		for (k=0;str[k];k++)
		{
			s[j++]=str[k];
		}
		s[j++]=i+2;
	}
	s[j]='A'-1;
	n=j+1;
	makesa();
	lcp();
	for (i=n-1,j=0;i>=0;i--)
	{
		if (s[i]<'A')
			j=0;
		else
			j++;
		len[i]=j;	
	}
	int sum=0;
	for (i=0;i<n;i++)
	{
		sum+=len[sa[i]]-height[i];
	}
	map<int,int>::iterator it;
	scanf("%d",&q);
	while (q--)
	{
		scanf("%d",&m);
		if (m>sum||m<1)
		{
			printf("INVALIDn");
		}
		else
		{
			for (i=1,j=0;(j+=len[sa[i]]-height[i])<m;i++);
			while (sa[i]<0||sa[i]>n+1)
			{
			}
			j=len[sa[i]]-(j-m);
			i=sa[i];
			while (j--)
			{
				putchar(s[i]);
				i++;
			}
			puts("");
		}
	}
}

Problem solution in C.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void add(char **list, char *c, long long *size)
{
    int i, j;
    if( (*size) == 0 )
    {
        list[0] = c;
        (*size)++;
        return;
    }
    j = get_i(list, c, *size);
    if( j < 0 )
        return;
    for( i = (*size) ; i > j ; i-- )
        list[i] = list[i-1];
    list[j] = c;
    (*size)++;
    return;
}
int get_i(char **list, char *c, long long size)
{
    if( size == 0 )
        return 0;
    int i = strcmp(c, list[(size-1)>>1]);
    if( i > 0 )
        return get_i(&list[(size+1)>>1], c, size>>1) + ( (size+1) >> 1 );
    else if( i == 0 )
        return -1000000005;
    else
        return get_i(list, c, (size-1)>>1);
}
int mis(char *a, char *b)
{
    int i;
    for( i = 0 ; 1 ; i++ )
        if( a[i] != b[i] )
            return i;
}
int find_i(int *length_a, int c)
{
    int i;
    for( i = 0 ; 1 ; i++ )
        if( length_a[i] >= c )
            return i;
}
int main()
{
    int i, j, k, n, q, length, index1, index2;
    long long size = 0;
    char c[50][2001], temp, **list;
    list = (char**)malloc(sizeof(char*) * 1000000);
    scanf("%d", &n);
    for( i = 0 ; i < n ; i++ )
    {
        scanf("%s", &c[i][0]);
        length = strlen(&c[i][0]);
        for( j = 0 ; j < length ; j++ )
            add(list, &c[i][j], &size);
    }
    int mis_a[size], length_a[size];
    mis_a[0] = 0;
    length_a[0] = strlen(list[0]);
    for( i = 1 ; i < size ; i++ )
    {
        mis_a[i] = mis(list[i], list[i-1]);
        length_a[i] = length_a[i-1] + strlen(list[i]) - mis_a[i];
    }
    scanf("%d", &q);
    for( i = 0 ; i < q ; i++ )
    {
        scanf("%d", &k);
        if( k > length_a[size-1] )
            printf("INVALIDn");
        else
        {
            index1 = find_i(length_a, k);
            if( index1 == 0 )
                index2 = k;
            else
                index2 = k - length_a[index1-1] + mis_a[index1];
            temp = (list[index1])[index2];
            (list[index1])[index2] = '';
            printf("%sn", list[index1]);
            (list[index1])[index2] = temp;
        }
    }
    return 0;
}