# Find Strings – HackerRank Solution

In this post, we will solve Find Strings HackerRank Solution. This problem (Find Strings) is a part of HackerRank Problem Solving series.

## Solution – Find Strings – HackerRank Solution

### C++

```#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <sstream>
#include <cmath>
#include <string>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <list>
#include <set>
#include <map>
using namespace std;

#define MAXN 1000005
int n,t;
int p[MAXN],r[MAXN],h[MAXN];
string s;
void fix_index(int *b, int *e) {
int pkm1, pk, np, i, d, m;
pkm1 = p[*b + t];
m = e - b; d = 0;
np = b - r;
for(i = 0; i < m; i++) {
if (((pk = p[*b+t]) != pkm1) && !(np <= pkm1 && pk < np+m)) {
pkm1 = pk;
d = i;
}
p[*(b++)] = np + d;
}
}

bool comp(int i, int j) {
return p[i + t] < p[j + t];
}
void suff_arr() {
int i, j, bc[256];
t = 1;
for(i = 0; i < 256; i++) bc[i] = 0;  //alfabeto
for(i = 0; i < n; i++) ++bc[int(s[i])]; //counting sort inicial del alfabeto
for(i = 1; i < 256; i++) bc[i] += bc[i - 1];
for(i = 0; i < n; i++) r[--bc[int(s[i])]] = i;
for(i = n - 1; i >= 0; i--) p[i] = bc[int(s[i])];
for(t = 1; t < n; t *= 2) {
for(i = 0, j = 1; i < n; i = j++) {
while(j < n && p[r[j]] == p[r[i]]) ++j;
if (j - i > 1) {
sort(r + i, r + j, comp);
fix_index(r + i, r + j);
}
}
}
}
//Longest Common Preffix
void lcp() {
int tam = 0, i, j;
for(i = 0; i < n; i++)if (p[i] > 0) {
j = r[p[i] - 1];
while(s[i + tam] == s[j + tam]) ++tam;
h[p[i]] = tam;
if (tam > 0) --tam;
}
h[0] = 0;
}

int main(){
int numS=0; scanf("%d",&numS);
int res=numS;
string sTemp;
while(res--){
cin>>sTemp;
s +=sTemp+char(res+1);
}
n=s.size();
suff_arr();
lcp();
vector<int> l(n);
//Compute the l'
for (int i = n-1,acum=1; i >= 0; --i)
{
if(s[i]<'a')
acum=0;
l[p[i]]=acum;
acum++;

}
int q;scanf("%d",&q);
while(q--){
int k,i=1;
scanf("%d",&k);
for (; i < n; ++i)
{
int comp = l[i]-h[i];
if(comp>=k){
cout<<s.substr(r[i],h[i]+k)<<endl;
break;
}else{
k-=comp;
}
}
if(i==n)
cout<<"INVALID"<<endl;
}

return 0;
}
```

### 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 = []

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

### Java

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

public class Solution {
static TreeSet<String>t;
public static void main(String[] args) {
try{
t=new TreeSet<String>();
for(int i=0;i<n;i++){
for(int j=0;j<s.length();j++){
}
}
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;
}
for(int i=0;i<q;i++){
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);
}

}

}
```

Note: This problem (Find Strings) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.