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.

Function Description

Complete the findStrings function in the editor below. It should return array of strings.

findStrings has the following parameter(s):

• w: an array of strings
• queries: an array of integers

Input Format

The first line contains an integer n, the number of strings in the array w.
Each of the next n lines consists of a string w[i].
The next line contains an integer q, the number of queries.
Each of the next q lines consists of a single integer k.

HackerRank Find Strings 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()

Find Strings 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;
}