Header Ad

HackerRank Similar Strings problem solution

In this HackerRank Similar Strings problem solution, we have given a string S of size n and given us q queries to perform on the string where each query is in the form of a pair of integers(l,r). and for each substring S[l,r] we need to find the number of substrings S[x,y] where substrings S[l,r] is similar to substring S[x,y] and we need to print this number on a new line.

HackerRank Similar Strings problem solution


Problem solution in Java.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {
    static final int NUM_CHARS = 11;
    static final int ENCODE_LENGTH = 85;
   
    static long encode(final char[] chars, final int start, final int checkLength) {
        final int length = Math.min(checkLength, chars.length-1);
        long hash = 31;//5381;
        int[] sim = new int[NUM_CHARS];
        int count = 1;
        int i=start;
        for(; i <= start+length && i < chars.length; i++) {
            int sim_index = chars[i] - 'a';
            if(sim[sim_index] == 0) {
                sim[sim_index] = count;
                count++;
            }
            hash = hash * sim[sim_index] + 33;
        }
        return hash;
    }
    
    static Map<Long, List<Integer>> buildIndex(final char[] chars) {
        Map<Long, List<Integer>> index = new HashMap<>();
        
        for(int i = 0; i < chars.length - ENCODE_LENGTH; i++) {
            final long encoded = encode(chars, i, ENCODE_LENGTH);
            List<Integer> indexes = index.get(encoded);
            if(indexes == null) {
                indexes = new LinkedList<>();
                index.put(encoded, indexes);
            }
            indexes.add(i);
        }
        
        return index;
    }
    
    static boolean isSimilar(final char[] chars, final int aStart, final int aEnd, final int bOffset) {
        final int checkLength = aEnd - aStart + 1;
        int[] simI = new int[NUM_CHARS+1];
        int[] simJ = new int[NUM_CHARS+1];
        for(int i=0; i < checkLength; i++) {
            int indexI = chars[i+aStart] - 'a' + 1;
            int indexJ = chars[i+bOffset] - 'a' + 1;
            if(simI[indexI] == 0 && simJ[indexJ] == 0) {
                simI[indexI] = indexJ;
                simJ[indexJ] = indexI;
            } else if(simI[indexI] != indexJ || simJ[indexJ] != indexI)
                return false;
        }
        return true;
    }
    
    /*
     * Complete the similarStrings function below.
     */
    static int similarStrings(final char[] chars, int start, int end, Map<Long, List<Integer>> charIndex) {
        final int sLength = chars.length;
        final int checkLength = end - start + 1;
        int answer = 0;
        if(checkLength == 1)
            answer = sLength;
        else if(checkLength == ENCODE_LENGTH) {
            List<Integer> indexes = charIndex.get(encode(chars,start-1, ENCODE_LENGTH));
            answer = indexes == null ? 1 : indexes.size();
        } else if(checkLength < ENCODE_LENGTH) {
            for(int index=0; index <= sLength - checkLength; index++)
                if(index == start-1 ||
                   isSimilar(chars, start-1, end-1, index))
                    answer++;
        } else {
            List<Integer> indexes = charIndex.get(encode(chars,start-1,ENCODE_LENGTH));
            if(indexes == null)
                answer = 1;
            else {
                for(Integer index : indexes) {
                    if(index + checkLength > chars.length) {
                        break;
                    } else if(index == start-1 ||
                              isSimilar(chars, start-1, end-1, index))
                        answer++;
                }
            }
            if(answer == 0)
                answer = 1;
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        final Scanner input = new Scanner(System.in);

        String[] nq = input.nextLine().split(" ");
        final int n = Integer.parseInt(nq[0].trim());
        final int q = Integer.parseInt(nq[1].trim());

        final String s = input.nextLine().trim();
        final char[] sChars = s.toCharArray();
        final Map<Long, List<Integer>> index = buildIndex(sChars);

        StringBuilder answer = new StringBuilder(q*3);
        for (int queriesRowItr = 0; queriesRowItr < q; queriesRowItr++) {
            final int l = input.nextInt();
            final int r = input.nextInt();
            
            final int result = similarStrings(sChars, l, r, index);

            answer.append(result);
            answer.append('\n');
        }
        System.out.print(answer.toString());
        
        input.close();
    }
}

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


Problem solution in C++.

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int N = 5E4 * 10 * 2, M = N;

int t[M][2], len[M] = {0}, fa[M], sz = 2, last = 1;
char* one[M];
void ins(int ch, char* pp) {
    int p = last, np = 0, nq = 0, q = -1;
    if (!t[p][ch]) {
        np = sz++; one[np] = pp;
        len[np] = len[p] + 1;
        for (; p && !t[p][ch]; p = fa[p]) t[p][ch] = np;
    }
    if (!p) fa[np] = 1;
    else {
        q = t[p][ch];
        if (len[p] + 1 == len[q]) fa[np] = q;
        else {
            nq = sz++; len[nq] = len[p] + 1; one[nq] = one[q];
            memcpy(t[nq], t[q], sizeof t[0]);
            fa[nq] = fa[q];
            fa[np] = fa[q] = nq;
            for (; t[p][ch] == q; p = fa[p]) t[p][ch] = nq;
        }
    }
    last = np ? np : nq ? nq : q;
}
int up[M], c[256] = {2}, aa[M];
vector<int> G[M];
void rsort() {
    FOR (i, 1, 256) c[i] = 0;
    FOR (i, 2, sz) up[i] = *(one[i] + len[fa[i]]);
    FOR (i, 2, sz) c[up[i]]++;
    FOR (i, 1, 256) c[i] += c[i - 1];
    FOR (i, 2, sz) aa[--c[up[i]]] = i;
    FOR (i, 2, sz) G[fa[aa[i]]].push_back(aa[i]);
}

int idx[N], clk, dfn_p, dfn[N * 2][22], rdfn[N], dep[N];
void dfs(int u) {
    idx[u] = ++clk;
    rdfn[u] = dfn_p; dfn[dfn_p++][0] = u;
    for (int& v: G[u]) {
        dep[v] = dep[u] + 1;
        dfs(v);
        dfn[dfn_p++][0] = u;
    }
}
inline int highbit(int x) { return 31 - __builtin_clz(x); }
inline int dmin(int a, int b) { return dep[a] < dep[b] ? a : b; }
void rmq_init() {
    FOR (x, 1, highbit(dfn_p) + 1)
        FOR (i, 0, dfn_p - (1 << x) + 1)
            dfn[i][x] = dmin(dfn[i][x - 1], dfn[i + (1 << (x - 1))][x - 1]);
}
int lca(int u, int v) {
    u = rdfn[u]; v = rdfn[v]; if (u > v) swap(u, v);
    int t = highbit(v - u + 1);
    return dmin(dfn[u][t], dfn[v - (1 << t) + 1][t]);
}

char s[N];
int ed[10][N], mp[N][10];
char a[10][N];
struct P { int u, c; };
P p[N][10];

int n;
int lcp(int a, int b) {
    int ret = N;
    FOR (c, 0, 10) ret = min(ret, len[lca(p[a][c].u, p[b][c].u)]);
    return min(ret, min(n - a, n - b));
}

bool cmp(int x, int y) {
    int l = lcp(x, y);
    if (x + l >= n || y + l >= n) return x > y;
    return mp[x][s[x + l] - 'a'] < mp[y][s[y + l] - 'a'];
}
int sa[N], rk[N];

int main() {
    int Qn; cin >> n >> Qn;
    scanf("%s", s);
    FOR (c, 0, 10) {
        last = 1;
        FORD (i, n - 1, -1) {
            a[c][i] = s[i] - 'a' == c ? 0 : 1;
            ins(a[c][i], &a[c][i]);
            ed[c][i] = last;
        }
    }
    rsort();
    dfs(1);
    rmq_init();
    FOR (i, 0, n) {
        FOR (c, 0, 10) p[i][c] = {ed[c][i], c};
        sort(p[i], p[i] + 10, [](const P& a, const P& b){ return idx[a.u] < idx[b.u]; });
        FOR (c, 0, 10) mp[i][p[i][c].c] = c;
    }
    FOR (i, 0, n) sa[i] = i;
    sort(sa, sa + n, cmp);
    dbg(lcp(4, 6));
    FOR (i, 0, n - 1) dbg(sa[i], sa[i + 1], lcp(sa[i], sa[i + 1]));
    FOR (i, 0, n) rk[sa[i]] = i;
    while (Qn--) {
        int L, R; scanf("%d%d", &L, &R); --L; --R;
        int len = R - L + 1;
        int l = 0, r = rk[L], ll = -1, rr = -1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (lcp(L, sa[m]) >= len) { ll = m; r = m - 1; }
            else l = m + 1;
        }
        l = rk[L]; r = n - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (lcp(L, sa[m]) >= len) { rr = m; l = m + 1; }
            else r = m - 1;
        }
        dbg(ll, rr, rk[L]);
        printf("%d\n", rr - ll + 1);
    }
}

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


Problem solution in C.

#include <stdio.h>
#include <malloc.h>
#define rint register int
typedef unsigned short ushort;
char* TVA;
char* S;
int n;
int cmpPos(const void*pa,const void*pb){
    rint a = *((ushort*)pa);
    rint b = *((ushort*)pb);
    int r = 1;
    if(a>b){
        r = a;
        a = b;
        b = r;
        r = -1;
    }    
    char* VA = TVA+ a*10;
    char* VB = TVA + b*10;
    for(;b<n;a++,b++){
        int dr = (int)VA[S[a]] - (int)VB[S[b]];
        if(dr) return dr*r;
    }
    return r;
}

inline int sameLen(int pa,int pb){
    rint a = pa;
    rint b = pb;
    if(a>b){
        a ^= b;
        b ^= a;
        a ^= b;
    }
    pa = a;
    char* VA = TVA+a*10;
    char* VB = TVA+b*10;
    for(;b<n;a++,b++)
        if(VA[S[a]] != VB[S[b]]) return a - pa;
    return a-pa;
}

int main(void) {
    int q;
    scanf("%d %d",&n,&q);
    S = (char*)malloc(sizeof(char)*(n+1));
    scanf("%s",S);
    S[n] = -1;
    for(rint i=0;i<n;i++) S[i] -= 'a';
    TVA = (char*)malloc(sizeof(char)*(n+1)*10);
    for(rint i =0;i<10;i++) TVA[i+(n)*10] = i;
    for(rint i=n-1;i>=0;i--){
        char* TVAi = TVA + i*10;
        char sip = TVAi[S[i]+10];
        for(rint j=0;j<10;j++){
            if(TVAi[j+10] < sip) TVAi[j] = TVAi[j+10] + 1;
            else TVAi[j] = TVAi[j+10];
        }
        TVAi[S[i]] = 0;
    }
    ushort* SA = (ushort*)malloc(sizeof(ushort)*n);
    for(rint i=0;i<n;i++) SA[i] = (ushort)i;
    qsort(SA,n,sizeof(ushort),cmpPos);
    ushort* SB = (ushort*)malloc(sizeof(ushort)*n);
    ushort* KB = (ushort*)malloc(sizeof(ushort)*n);
    for(rint i=1;i<n;i++){
        SB[i] = sameLen(SA[i-1],SA[i]);
        KB[SA[i]] = i;
    }
    for(int w=0;w<q;w++){
        int x,y;
        scanf("%d %d",&x,&y);
        int d = y - x + 1;
        rint tx = KB[x-1];
        while(tx>0 && SB[tx]>=d) tx--;
        rint ty = KB[x-1]+1;
        while(ty<n && SB[ty]>=d) ty++;
        printf("%d\n",ty-tx);
    }
    return 0;
}

{"mode":"full","isActive":fa


Post a Comment

0 Comments