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.

HackerRank Find Strings problem solution


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()

{"mode":"full","isActive":false}


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);        
        }

    }

}

{"mode":"full","isActive":false}


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("INVALID\n");
		}
		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("");
		}
	}
}

{"mode":"full","isActive":false}


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("INVALID\n");
        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] = '\0';
            printf("%s\n", list[index1]);
            (list[index1])[index2] = temp;
        }
    }
    return 0;
}

{"mode":"full","isActive":false}