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.
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();
}
}
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 << " 33[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << " 33[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("%dn", rr - ll + 1);
}
}
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("%dn",ty-tx);
}
return 0;
}
