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

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

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

    }

}

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.