Find Strings – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Find Strings HackerRank Solution
#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <cstring>
struct Suffix
{
const char* m_str;
int m_lcp;
int m_size;
Suffix(const char* str)
: m_str(str)
, m_lcp(0)
, m_size(strlen(str))
{
};
int size() const
{
return m_size;
}
struct less
{
bool operator() (const Suffix* lhs, const Suffix* rhs)
{
return strcmp(lhs->m_str, rhs->m_str) < 0;
}
};
};
struct Node
{
typedef std::set<Suffix*, Suffix::less> Strings;
Strings m_strings;
void add_suffix(const char* start)
{
const char c = *start;
if (c == 0)
return;
m_strings.insert(new Suffix(start));
}
void prep_lcp()
{
if (m_strings.empty())
return;
Strings::const_iterator it = m_strings.begin();
Strings::iterator next = m_strings.begin();
for (++next; next != m_strings.end() ; ++next, ++it)
{
const char* c1 = (*it)->m_str;
const char* c2 = (*next)->m_str;
while (*c1 && *c2)
{
if (*c1 != *c2)
break;
(*next)->m_lcp += 1;
++c1;
++c2;
}
}
}
// need lcp
std::string get_n(int num)
{
Strings::const_iterator it = m_strings.begin();
for (; it != m_strings.end() ; ++it)
{
const Suffix* suff = *it;
num += suff->m_lcp;
if (num <= suff->size())
{
return std::string(suff->m_str, suff->m_str + num);
}
num -= suff->size();
}
return std::string("INVALID");
}
};
int main(int argc, char* argv[])
{
Node root;
int count = 0;
std::cin >> count;
std::vector<std::string> strings;
for (int i=0 ; i<count ; ++i)
{
std::string str;
std::cin >> str;
strings.push_back(str);
std::string& pushed = *strings.rbegin();
const size_t size = pushed.size();
const char* string = pushed.c_str();
for (int j=0 ; j<size ; ++j)
{
// the add_substr method will add all of the intermediate strings as well
// just my adding the longest case of the word you get all the others
root.add_suffix(string + j);
}
}
root.prep_lcp();
int queries = 0;
std::cin >> queries;
for (int i=0 ; i<queries ; ++i)
{
int index;
std::cin >> index;
std::cout << root.get_n(index) << std::endl;
}
return 0;
}
Java Find Strings HackerRank Solution
import java.io.* ;
import java.text.DecimalFormat;
import java.util.*;
import static java.lang.Math.* ;
import static java.util.Arrays.* ;
public class Solution {
public static void main(String[] args) {
new Solution().solveProblem();
out.close();
}
static Scanner in = new Scanner(new InputStreamReader(System.in));
static PrintStream out = new PrintStream(new BufferedOutputStream(System.out));
//static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int[] maxx ;
String s ="";
public void solveProblem() {
int n = in.nextInt() ;
in.nextLine() ;
String[] sn = new String[n] ;
for( int i = 0 ; i < n ; i++ ){
sn[i] = in.nextLine() + "A" ;
s += sn[i];
}
T = s.toCharArray() ;
maxx = new int[T.length] ;
int som = 0 ;
for( int i = 0 ; i < n ; i++ ){
int nu = sn[i].length() ;
for( int j = som ; j < som + nu ; j++)
maxx[j] = som + nu ;
som += nu ;
}
//System.out.println(Arrays.toString(maxx));
this.n = T.length ;
constructSA() ;
computeLCP() ;
int q = in.nextInt() ; in.nextLine() ;
for( int i = 0 ; i < q ; i++ )
losOp(in.nextLong()) ;
}
void losOp( long k ) {
int start = 0 ;
for( int i = 0 ; i < n ; i++ ){
int ind = SA[i] ;
start = LCP[i] ;
long aantal = max(0,maxx[ind] - 1 - ind - start) ;
//System.out.println("Zoek " + s.substring(ind) + " " + ind + " " + aantal + " " + start);
if( T[ind] != 'A' && aantal >= k ){
out.println(s.substring(ind, (int) (ind+start+k))) ;
return ;
}else if( T[ind] != 'A')
k -= aantal ;
//System.out.println(k);
}
out.println("INVALID") ;
}
int maxlen = 100010 ;
int n ;
char[] T ;
int[] RA = new int[maxlen] ;
int[] RATemp = new int[maxlen] ;
int[] SA = new int[maxlen] ;
int[] SATemp = new int[maxlen] ;
int[] c = new int[maxlen] ;
void constructSA(){
for( int i = 0 ; i < n ; i++ ){
RA[i] = T[i]-'.' ;
SA[i] = i ;
}
for( int k = 1 ; k < n ; k <<= 1 ){
countingSort( k ) ;
countingSort( 0 ) ;
RATemp[SA[0]] = 1 ;
int r = 1 ;
for( int i = 1 ; i < n ; i++ ){
RATemp[SA[i]] = ( RA[SA[i]] == RA[SA[i-1]] && RA[SA[i]+k] == RA[SA[i-1]+k] ) ? r : ++r ;
}
RA = RATemp.clone() ;
}
}
void countingSort( int k ){
int sum = 0 ;
int maxi = max( 300, n ) ;
fill( c, 0 ) ;
for( int i = 0 ; i < n ; i++ )
c[ ( i + k ) < n ? RA[i+k] : 0 ]++ ;
for( int i = 0 ; i <= maxi ; i++ ){
int t = c[i] ;
c[i] = sum ;
sum += t ;
}
for( int i = 0 ; i < n ; i++ ){
SATemp[c[(SA[i] + k) < n ? RA[SA[i]+k] : 0]++ ] = SA[i] ;
}
SA = SATemp.clone() ;
}
int[] Phi ;
int[] LCP ;
int max = 0 ;
void computeLCP(){
LCP = new int[n] ;
Phi = new int[n] ;
int[] PLCP = new int[n] ;
Phi[SA[0]] = -1 ;
for( int i = 1 ; i < n ; i++ )
Phi[SA[i]] = SA[i-1] ;
int L = 0;
for( int i = 0 ; i < n ; i++){
if( Phi[i] == -1){
PLCP[i] = 0 ;
continue ;
}
while( i+L < n && Phi[i]+L < n && T[i+L] == T[Phi[i]+L])
L++ ;
max = max(max,L) ;
PLCP[i] = L ;
L = max(L-1,0) ;
}
for( int i =1 ; i < n ; i++ )
LCP[i] = PLCP[SA[i]] ;
}
}
Python 3 Find Strings HackerRank Solution
import sys
data = sys.stdin.readlines()
def get_suffixes(string):
suffixes = set()
string_len = len(string)
for index in range(0, string_len):
suffixes.add(string[index: string_len])
return suffixes
def get_longest_common_prefix(string1, string2):
longest_common_index = 0
for index in range(len(string1)):
try:
if(string1[index] != string2[index]):
return string1[0: longest_common_index]
else:
longest_common_index = longest_common_index + 1
except IndexError:
return string1[0: longest_common_index]
def compute_cumulative_substrings_count(suffixes):
result = []
for index in range(len(suffixes)):
suffix = suffixes[index]
substrings_count = len(suffix)
previous_cumulative_substrings_count, previous_suffix = result[index - 1] if index != 0 else (0, '')
length_of_longest_common_prefix = len(get_longest_common_prefix(suffix, previous_suffix))
substrings_count = substrings_count - length_of_longest_common_prefix
result.append((previous_cumulative_substrings_count + substrings_count, suffix))
return result
def binary_search_for_nearest_big_number(array, number):
left_edge = 0
right_edge = len(array) - 1
if(number < 0 or number > array[right_edge]):
return None
if(number <= array[0]):
return 0
while right_edge - left_edge > 1:
mid_index = (left_edge + right_edge) // 2
mid_val = array[mid_index]
if(mid_val < number):
left_edge = mid_index
elif(mid_val > number):
right_edge = mid_index
elif(mid_val == number):
return mid_index
if(array[left_edge] == number):
return left_edge
return right_edge
def parse_input():
no_of_strings = int(data[0])
strings_input, queries_input = data[:no_of_strings + 1], data[no_of_strings + 1:]
strings = [strings_input[index].strip() for index in range(1, no_of_strings + 1)]
no_of_queries = int(queries_input[0])
queries = [int(queries_input[index]) for index in range(1, no_of_queries + 1)]
return (strings, queries)
def find_strings():
strings, queries = parse_input()
suffixes = set()
[suffixes.update(get_suffixes(string)) for string in strings]
suffixes_with_cumulative_substrings_count = compute_cumulative_substrings_count(sorted(list(suffixes)))
cumulative_substrings_count = [count for count, suffix in suffixes_with_cumulative_substrings_count]
for query in queries:
index = binary_search_for_nearest_big_number(cumulative_substrings_count, query)
if(index == None):
print('INVALID')
else:
cumulative_index, suffix = suffixes_with_cumulative_substrings_count[index]
previous_cumulative_index, previous_suffix = suffixes_with_cumulative_substrings_count[index - 1] if index != 0 else (0, '')
delta_index = query - previous_cumulative_index
if(delta_index == 0):
print(suffix)
else:
longest_common_prefix = get_longest_common_prefix(suffix, previous_suffix)
len_of_longest_common_prefix = len(longest_common_prefix)
print(longest_common_prefix + suffix[len_of_longest_common_prefix: len_of_longest_common_prefix + delta_index])
find_strings()
Python 2 Find Strings HackerRank Solution
#!/usr/bin/env python
from itertools import repeat, izip
from bisect import bisect_left
def sort_suff(ss):
sub_ss = set()
for s in ss:
for i in xrange(len(s)):
sub_ss.add(buffer(s, i, len(s) - i))
return sorted(sub_ss)
def get_lcp(s1, s2):
retval = 0
for c1, c2 in izip(s1, s2):
if c1 == c2: retval += 1
else: break
return retval
def get_rank(suff_arr):
rank = []
for i, suff in enumerate(suff_arr):
if i == 0:
rank.append(len(suff) - 1)
if i > 0:
prev_suff = suff_arr[i-1]
lcp = get_lcp(prev_suff, suff)
rank.append(rank[-1] + len(suff[lcp:]))
return rank
n = int(raw_input())
ss = []
for _ in xrange(n):
ss.append(raw_input())
suff_arr = sort_suff(ss)
rank = get_rank(suff_arr)
def query(k):
closet_rank_idx = bisect_left(rank, k)
if closet_rank_idx == len(rank):
return 'INVALID'
closet_rank = rank[closet_rank_idx]
suff = suff_arr[closet_rank_idx]
if closet_rank == k:
return suff
else:
return suff[:k - closet_rank]
q = int(raw_input())
for _ in xrange(q):
k = int(raw_input())
print query(k-1)
C Find Strings HackerRank Solution
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <errno.h>
char input[3000], output[3000];
int queries[600];
int malloc_cnt = 0;
//HASH table for ints implementation
typedef struct bucket_item{
int key;
char *val;
struct bucket_item *next;
} HASH_NODE;
#define HASH_MODULUS 997
HASH_NODE* hash_arr[HASH_MODULUS];
int calc_hash(int i) {
return (i % HASH_MODULUS);
}
HASH_NODE *get_hash_table_entry(int i) {
int hash = calc_hash(i);
HASH_NODE *item = hash_arr[hash];
if(item == NULL) { return NULL; }
while(item) {
if(item->key == i) { return item; }
item = item->next;
}
return NULL;
}
void insert_into_hash_table(int i) {
if(get_hash_table_entry(i) != NULL) { return; }
int hash = calc_hash(i);
HASH_NODE *new_node = malloc(sizeof(HASH_NODE));
new_node->key = i;
new_node->val = malloc(sizeof(char) * 2200);
new_node->next = NULL;
strcpy(new_node->val, "INVALID");
if(hash_arr[hash] == NULL) {
hash_arr[hash] = new_node;
} else {
new_node->next = hash_arr[hash];
hash_arr[hash] = new_node;
}
}
void print_keys_in_hash_table() {
int i;
HASH_NODE *tmp;
printf("HASH TABLE ENTRIES\n");
for(i = 0; i < HASH_MODULUS; i++) {
tmp = hash_arr[i];
while(tmp) {
printf("%d\n", tmp->key);
tmp = tmp->next;
}
}
printf("HASH TABLE ENTRIES OVER\n");
}
//
typedef struct node{
char *word;
int len;
struct node *children[26];
}NODE;
typedef void (*TRAVERSE_FUNC) (char *, int);
NODE* tree_root;
int prefix_match_cnt(char * str1, char *str2, int len1, int len2) {
int i = 0;
while((i < len1) && (i < len2) && (*str1++ == *str2++)) {
i++;
}
return i;
}
NODE* create_node(char *str, int len) {
int i;
NODE *tmp = malloc(sizeof(NODE));
tmp->word = str;
tmp->len = len;
for(i = 0; i < 26; i++) {
tmp->children[i] = NULL;
}
malloc_cnt++;
return tmp;
}
void add_suffix_string_to_tree(NODE *node, NODE *par_node, char *str, int len) {
int i, match_cnt;
NODE* new_node;
if(len == 0) { return; }
if(node->len != -1) { //node->len = -1 ==> root
match_cnt = prefix_match_cnt(str, node->word, len, node->len);
if(match_cnt == len) { return; } //The string is already present in the tree. return
//we are here ==> (match_cnt < len), (match_cnt <= node->len).
str = &str[match_cnt];
len -= match_cnt;
if(match_cnt < node->len) {
//split the current node with match_cnt length
new_node = create_node(node->word, match_cnt);
par_node->children[node->word[0] - 'a'] = new_node;
node->word += match_cnt;
node->len -= match_cnt;
new_node->children[node->word[0] - 'a'] = node;
node = new_node;
}
}
i = (str[0] - 'a');
if(node->children[i] == NULL) {
node->children[i] = create_node(str, len);
} else {
add_suffix_string_to_tree(node->children[i], node, str, len);
}
}
void add_all_suffixes_to_tree(NODE *root, char *str) {
int i, len = strlen(str);
for(i = 0; i < len; i++) {
add_suffix_string_to_tree(root, NULL, &str[i], (len - i));
}
}
void traverse_all_substrings(NODE *node, char *out, int len, TRAVERSE_FUNC func) {
int i;
if(node == NULL) { return; }
if(node->len == -1) {
for(i = 0; i < 26; i++) {
traverse_all_substrings(node->children[i], out, len, func);
}
} else {
strncpy(&out[len], node->word, node->len);
for(i = 0; i < node->len; i++) {
func(out, len + (i + 1));
}
for(i = 0; i < 26; i++) {
traverse_all_substrings(node->children[i], out, len + (node->len), func);
}
}
}
void print_substring(char *str, int len) {
char c = str[len];
str[len] = '\0';
printf("%s\n", str);
str[len] = c;
}
int total_substr_cnt = 0;
void cnt_substrings(char *str, int len) {
total_substr_cnt++;
}
int substr_cnt = 0;
void handle_substring(char *str, int len) {
char c = str[len];
HASH_NODE *item;
substr_cnt++;
item = get_hash_table_entry(substr_cnt);
if(item) {
str[len] = '\0';
strcpy(item->val, str);
str[len] = c;
return;
}
}
char* chomp(char * str) {
int len = strlen(str);
if((len > 0) && (str[len - 1] == '\n')) { str[len - 1] = '\0'; }
if((len > 1) && (str[len - 2] == '\r')) { str[len - 2] = '\0'; }
return str;
}
char* convert_to_lower(char* str) {
int len = strlen(str), i;
for(i = 0; i < len; i++) {
str[i] = tolower(str[i]);
}
return str;
}
FILE *file_open(char *filename, char *mode) {
FILE *fp = fopen(filename, mode);
if(fp == NULL) {
perror("file_open");
exit(0);
}
return fp;
}
int main(int argc, char **argv) {
int num_words, num_queries, tmp;
char *str;
int query_idx = 0, idx;
HASH_NODE *item;
FILE *fp = stdin;
if(argc > 1) {
fp = file_open(argv[1], "r");
}
fgets(input, 3000, fp);
num_words = tmp = atoi(input);
tree_root = create_node(NULL, -1); //Root marker
while(tmp > 0) {
tmp--;
fgets(input, 3000, fp);
chomp(input);
convert_to_lower(input);
//printf("Adding \"%s\" ....", input);
str = malloc(sizeof(char) * 3000);
strcpy(str, input);
add_all_suffixes_to_tree(tree_root, str);
//printf("Done\n");
}
total_substr_cnt = 0;
traverse_all_substrings(tree_root, output, 0, cnt_substrings);
fgets(input, 3000, fp);
num_queries = tmp = atoi(input);
while(tmp > 0) {
tmp--;
fgets(input, 3000, fp);
chomp(input);
queries[query_idx] = atoi(input);
insert_into_hash_table(queries[query_idx]);
query_idx++;
}
substr_cnt = 0;
traverse_all_substrings(tree_root, output, 0, handle_substring);
for(idx = 0; idx < query_idx; idx++) {
item = get_hash_table_entry(queries[idx]);
printf("%s\n", item->val);
}
return 0;
}