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.
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()
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("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("");
}
}
}
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;
}
0 Comments