Table of Contents
Similar Strings – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Similar Strings HackerRank Solution
#define _CRT_SECURE_NO_WARNINGS
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <memory.h>
#include <assert.h>
#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define eps 1e-9
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 350
using namespace std;
const int INF = 1e9;
const int N = 150031;
int n, tests;
string st;
int used[N];
int mapp[N];
vector<int> v;
int whr[N];
int pw[N];
int S[200000][15];
int maps1[200], maps2[200];
vector<int> entries[100];
int maps[4][100];
int FE[N][15];
void run_mapper(int a,int b)
{
vector<pair<int, int> > O;
for (int i = 0; i < 10; i++)
{
int whr = FE[a][i];
O.push_back(make_pair(whr, i));
}
sort(O.begin(), O.end());
for (int i = 0; i < O.size(); i++)
{
maps[b][O[i].second] = i;
}
}
int get_hash(int a, int span, int tp)
{
int res = 0;
for (int i = 0; i < 10; i++)
{
int here = S[a+span][i] - S[a][i];
here *= (maps[tp][i]+1);
here *= pw[N - a - 1];
res += here;
}
return res;
}
int lcp(int a, int b)
{
run_mapper(a, 1);
run_mapper(b, 2);
/*for (int i = 0; i < 10; i++)
{
cout << maps[1][i] << " ";
}
cout << endl;
for (int i = 0; i < 10; i++)
{
cout << maps[2][i] << " ";
}
cout << endl;
*/
int l, r;
l = 0;
r = st.size() - max(a, b);
while (l < r)
{
int mid = l + r + 1;
mid /= 2;
long long H1 = get_hash(a, mid,1);
long long H2 = get_hash(b, mid,2);
if (H1 == H2)
l = mid;
else
r = mid - 1;
}
return l;
}
bool cmp(int a, int b)
{
int Q = lcp(a, b);
if (a + Q == st.size())
return true;
if (b + Q == st.size())
return false;
int val1 = maps[1][st[a + Q]-'a'];
int val2 = maps[2][st[b + Q]-'a'];
// cout << val1 << "%%" << val2 << endl;
return val1 < val2;
}
int LL[N];
int sparse[N][20];
int Lcp(int a, int b)
{
if (a>b)
swap(a, b);
if (a == b)
return 1e9;
--b;
int q = 0;
while ((1 << q) * 2 < (b - a + 1))
++q;
return min(sparse[a][q], sparse[b - (1 << q) + 1][q]);
}
int main(){
//freopen("fabro.in","r",stdin);
//freopen("fabro.out","w",stdout);
//freopen("F:/in.txt", "r", stdin);
//freopen("F:/output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
//cin.tie(0);
cin >> n >> tests;
pw[0] = 1;
for (int i = 1; i < N; i++)
{
pw[i] = pw[i - 1] * 173;
}
cin >> st;
for (int i = 0; i < 10; i++)
{
FE[st.size()][i] = st.size();
}
for (int i = st.size() - 1; i >= 0; --i)
{
for (int j = 0; j < 10; j++)
{
FE[i][j] = FE[i + 1][j];
if (st[i] == j + 'a')
FE[i][j] = i;
}
}
for (int i = 0; i < st.size(); i++)
{
for (int j = 0; j < 10; j++)
{
S[i + 1][j] = S[i][j];
if (st[i] == j + 'a')
S[i + 1][j] += pw[i];
}
}
for (int i = 0; i < st.size(); i++)
{
v.push_back(i);
}
sort(v.begin(), v.end(),cmp);
for (int i = 0; i < v.size(); i++)
{
whr[v[i]] = i;
}
for (int i = 0; i+1 < v.size(); i++)
{
LL[i] = lcp(v[i], v[i + 1]);
}
for (int lev = 0; lev < 17; lev++)
{
for (int i = 0; i < v.size(); i++)
{
if (lev == 0)
sparse[i][lev] = LL[i];
else
{
sparse[i][lev] = sparse[i][lev - 1];
if (i + (1 << lev) / 2 <= st.size())
sparse[i][lev] = min(sparse[i][lev], sparse[i + (1 << lev) / 2][lev - 1]);
}
}
}
for (int i = 1; i <= tests; i++)
{
int l, r;
cin >> l >> r;
--l;
--r;
int span = r - l + 1;
int ps = whr[l];
l = ps;
r = v.size() - 1;
while (l < r)
{
int mid = l + r+1;
mid /= 2;
if (Lcp(ps,mid) >= span)
l = mid;
else
r = mid - 1;
}
int R = r;
r = ps;
l = 0;
while (l < r)
{
int mid = l + r;
mid /= 2;
if (Lcp(ps,mid) >= span)
r = mid;
else
l = mid + 1;
}
cout << R-l+1 << endl;
}
cin.get(); cin.get();
return 0;
}
Java Similar Strings HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.Map;
public class G {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
int n = ni(), Q = ni();
char[] s = ns(n);
int[][] next = makeNext(s, 'a', 'j');
int[][] snext = new int[n][];
for(int i = 0;i < n;i++){
int[] temp = new int[10];
for(int j = 0;j < 10;j++){
temp[j] = next[j][i]<<4|j;
}
Arrays.sort(temp);
for(int j = 0;j < 10;j++){
temp[j] &= 15;
}
snext[i] = temp;
}
int[][] isnext = new int[n][];
for(int i = 0;i < n;i++){
int[] temp = new int[10];
for(int j = 0;j < 10;j++){
temp[snext[i][j]] = j;
}
isnext[i] = temp;
}
char[] bin = new char[n*10];
Arrays.fill(bin, 'a');
for(int i = 0;i < n;i++){
bin[(s[i]-'a')*n+i] = (char)('a'+1);
}
int[] sa = sa(bin);
int[] lcp = buildLCP(bin, sa);
int[][] st = buildY(lcp);
Integer[] xsa = new Integer[n];
for(int i = 0;i < n;i++){
xsa[i] = i;
}
int[] isa = new int[bin.length];
for(int i = 0;i < isa.length;i++)isa[sa[i]] = i;
Arrays.sort(xsa, new Comparator<Integer>() {
public int compare(Integer a, Integer b) {
int minlcp = n+100;
int res = 0;
for(int j = 0;j < 10;j++){
int l = isa[snext[a][j]*n+a];
int r = isa[snext[b][j]*n+b];
if(l > r){
int d = l; l = r; r = d;
}
int llcp = Math.min(n-Math.max(a, b), rmq(st, lcp, l+1, r+1));
if(llcp < minlcp){
minlcp = llcp;
if(a+llcp >= n){
res = -1;
}else if(b+llcp >= n){
res = 1;
}else{
res = isnext[a][s[a+llcp]-'a'] - isnext[b][s[b+llcp]-'a'];
}
}
}
return res;
}
});
int[] xlcp = new int[n];
for(int i = 0;i < n-1;i++){
int a = xsa[i], b = xsa[i+1];
int minlcp = n+100;
for(int j = 0;j < 10;j++){
int l = isa[snext[a][j]*n+a];
int r = isa[snext[b][j]*n+b];
if(l > r){
int d = l; l = r; r = d;
}
int llcp = Math.min(n-Math.max(a, b), rmq(st, lcp, l+1, r+1));
if(llcp < minlcp){
minlcp = llcp;
}
}
xlcp[i+1] = minlcp;
}
// for(int i = 0;i < n;i++){
// tr(lexsort(Arrays.copyOfRange(s, i, n)));
// }
// tr(xsa);
// tr(xlcp);
int[] xisa = new int[n];
for(int i = 0;i < n;i++){
xisa[xsa[i]] = i;
}
SegmentTreeRMQ xst = new SegmentTreeRMQ(xlcp);
for(int z = 0;z < Q;z++){
int l = ni()-1, r = ni()-1;
int pos = xisa[l], len = r-l+1;
int aft = xst.firstle(pos+1, len-1);
if(aft == -1)aft = n;
int bef = xst.lastle(pos, len-1);
out.println(aft-bef);
}
}
public static int[] lexsort(char[] a)
{
Map<Character, Integer> map = new HashMap<>();
int[] ret = new int[a.length];
int id = 0;
for(int i = 0;i < a.length;i++){
if(!map.containsKey(a[i])){
map.put(a[i], id++);
}
ret[i] = map.get(a[i]);
}
return ret;
}
public static class SegmentTreeRMQ {
public int M, H, N;
public int[] st;
public SegmentTreeRMQ(int n)
{
N = n;
M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
H = M>>>1;
st = new int[M];
Arrays.fill(st, 0, M, Integer.MAX_VALUE);
}
public SegmentTreeRMQ(int[] a)
{
N = a.length;
M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
H = M>>>1;
st = new int[M];
for(int i = 0;i < N;i++){
st[H+i] = a[i];
}
Arrays.fill(st, H+N, M, Integer.MAX_VALUE);
for(int i = H-1;i >= 1;i--)propagate(i);
}
public void update(int pos, int x)
{
st[H+pos] = x;
for(int i = (H+pos)>>>1;i >= 1;i >>>= 1)propagate(i);
}
private void propagate(int i)
{
st[i] = Math.min(st[2*i], st[2*i+1]);
}
public int minx(int l, int r){
if(l >= r)return 0;
int min = Integer.MAX_VALUE;
while(l != 0){
int f = l&-l;
if(l+f > r)break;
int v = st[(H+l)/f];
if(v < min)min = v;
l += f;
}
while(l < r){
int f = r&-r;
int v = st[(H+r)/f-1];
if(v < min)min = v;
r -= f;
}
return min;
}
public int min(int l, int r){ return l >= r ? 0 : min(l, r, 0, H, 1);}
private int min(int l, int r, int cl, int cr, int cur)
{
if(l <= cl && cr <= r){
return st[cur];
}else{
int mid = cl+cr>>>1;
int ret = Integer.MAX_VALUE;
if(cl < r && l < mid){
ret = Math.min(ret, min(l, r, cl, mid, 2*cur));
}
if(mid < r && l < cr){
ret = Math.min(ret, min(l, r, mid, cr, 2*cur+1));
}
return ret;
}
}
public int firstle(int l, int v) {
int cur = H+l;
while(true){
if(st[cur] <= v){
if(cur < H){
cur = 2*cur;
}else{
return cur-H;
}
}else{
cur++;
if((cur&cur-1) == 0)return -1;
if((cur&1)==0)cur>>>=1;
}
}
}
public int lastle(int l, int v) {
int cur = H+l;
while(true){
if(st[cur] <= v){
if(cur < H){
cur = 2*cur+1;
}else{
return cur-H;
}
}else{
if((cur&cur-1) == 0)return -1;
cur--;
if((cur&1)==1)cur>>>=1;
}
}
}
}
public static int[][] build(int[] a)
{
int n = a.length;
int b = 32-Integer.numberOfLeadingZeros(n);
int[][] ret = new int[b][];
for(int i = 0, l = 1;i < b;i++, l*=2) {
if(i == 0) {
ret[i] = a;
}else {
ret[i] = new int[n-l+1];
for(int j = 0;j < n-l+1;j++) {
ret[i][j] = Math.min(ret[i-1][j], ret[i-1][j+l/2]);
}
}
}
return ret;
}
// [a,b)
public static int rmq(int[][] or, int a, int b)
{
if(a >= b)return 0;
// 1:0, 2:1, 3:1, 4:2, 5:2, 6:2, 7:2, 8:3
int t = 31-Integer.numberOfLeadingZeros(b-a);
return Math.min(or[t][a], or[t][b-(1<<t)]);
}
// yosupo table
static final int S = 3;
public static int[][] buildY(int[] a)
{
int n = a.length;
int[] ca = new int[(n>>>S)+1];
Arrays.fill(ca, Integer.MAX_VALUE);
for(int i = 0;i < n;i++){
if(a[i] < ca[i>>>S])ca[i>>>S] = a[i];
}
int[][] st = build(ca);
return st;
}
public static int rmq(int[][] st, int[] a, int l, int r)
{
if(l >= r)return 0;
if(l+(1<<S)-1>>>S >= r>>>S){
int ret = Integer.MAX_VALUE;
for(int i = l;i < r;i++){
if(a[i] < ret)ret = a[i];
}
return ret;
}
int t = 31-Integer.numberOfLeadingZeros((r>>>S)-(l+(1<<S)-1>>>S));
int ret = Math.min(st[t][l+(1<<S)-1>>>S], st[t][(r>>>S)-(1<<t)]);
while(l<<~S!=0){
if(a[l] < ret)ret = a[l];
l++;
}
while(r<<~S!=0){
r--;
if(a[r] < ret)ret = a[r];
}
return ret;
}
int[][] makeNext(char[] s, char inf, char sup)
{
int n = s.length;
int[][] next = new int[sup-inf+1][n+1];
for(int i = 0;i < sup-inf+1;i++)next[i][n] = n+1;
for(int i = s.length-1;i >= 0;i--){
for(int j = 0;j < sup-inf+1;j++)next[j][i] = next[j][i+1];
next[s[i]-inf][i] = i+1;
}
return next;
}
private static interface BaseArray {
public int get(int i);
public void set(int i, int val);
public int update(int i, int val);
}
private static class CharArray implements BaseArray {
private char[] m_A = null;
private int m_pos = 0;
CharArray(char[] A, int pos) {
m_A = A;
m_pos = pos;
}
public int get(int i) {
return m_A[m_pos + i] & 0xffff;
}
public void set(int i, int val) {
m_A[m_pos + i] = (char) (val & 0xffff);
}
public int update(int i, int val) {
return m_A[m_pos + i] += val & 0xffff;
}
}
private static class IntArray implements BaseArray {
private int[] m_A = null;
private int m_pos = 0;
IntArray(int[] A, int pos) {
m_A = A;
m_pos = pos;
}
public int get(int i) {
return m_A[m_pos + i];
}
public void set(int i, int val) {
m_A[m_pos + i] = val;
}
public int update(int i, int val) {
return m_A[m_pos + i] += val;
}
}
/* find the start or end of each bucket */
private static void getCounts(BaseArray T, BaseArray C, int n, int k) {
int i;
for(i = 0;i < k;++i){
C.set(i, 0);
}
for(i = 0;i < n;++i){
C.update(T.get(i), 1);
}
}
private static void getBuckets(BaseArray C, BaseArray B, int k, boolean end) {
int i, sum = 0;
if(end != false){
for(i = 0;i < k;++i){
sum += C.get(i);
B.set(i, sum);
}
}else{
for(i = 0;i < k;++i){
sum += C.get(i);
B.set(i, sum - C.get(i));
}
}
}
/* sort all type LMS suffixes */
private static void LMSsort(BaseArray T, int[] SA, BaseArray C,
BaseArray B, int n, int k) {
int b, i, j;
int c0, c1;
/* compute SAl */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, false); /* find starts of buckets */
j = n - 1;
b = B.get(c1 = T.get(j));
--j;
SA[b++] = (T.get(j) < c1) ? ~j : j;
for(i = 0;i < n;++i){
if(0 < (j = SA[i])){
if((c0 = T.get(j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
--j;
SA[b++] = (T.get(j) < c1) ? ~j : j;
SA[i] = 0;
}else if(j < 0){
SA[i] = ~j;
}
}
/* compute SAs */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, true); /* find ends of buckets */
for(i = n - 1, b = B.get(c1 = 0);0 <= i;--i){
if(0 < (j = SA[i])){
if((c0 = T.get(j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
--j;
SA[--b] = (T.get(j) > c1) ? ~(j + 1) : j;
SA[i] = 0;
}
}
}
private static int LMSpostproc(BaseArray T, int[] SA, int n, int m) {
int i, j, p, q, plen, qlen, name;
int c0, c1;
boolean diff;
/*
* compact all the sorted substrings into the first m items of SA 2*m
* must be not larger than n (proveable)
*/
for(i = 0;(p = SA[i]) < 0;++i){
SA[i] = ~p;
}
if(i < m){
for(j = i, ++i;;++i){
if((p = SA[i]) < 0){
SA[j++] = ~p;
SA[i] = 0;
if(j == m){
break;
}
}
}
}
/* store the length of all substrings */
i = n - 1;
j = n - 1;
c0 = T.get(n - 1);
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
for(;0 <= i;){
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
if(0 <= i){
SA[m + ((i + 1) >> 1)] = j - i;
j = i + 1;
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
}
}
/* find the lexicographic names of all substrings */
for(i = 0, name = 0, q = n, qlen = 0;i < m;++i){
p = SA[i];
plen = SA[m + (p >> 1)];
diff = true;
if((plen == qlen) && ((q + plen) < n)){
for(j = 0;(j < plen) && (T.get(p + j) == T.get(q + j));++j){
}
if(j == plen){
diff = false;
}
}
if(diff != false){
++name;
q = p;
qlen = plen;
}
SA[m + (p >> 1)] = name;
}
return name;
}
/* compute SA and BWT */
private static void induceSA(BaseArray T, int[] SA, BaseArray C,
BaseArray B, int n, int k) {
int b, i, j;
int c0, c1;
/* compute SAl */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, false); /* find starts of buckets */
j = n - 1;
b = B.get(c1 = T.get(j));
SA[b++] = ((0 < j) && (T.get(j - 1) < c1)) ? ~j : j;
for(i = 0;i < n;++i){
j = SA[i];
SA[i] = ~j;
if(0 < j){
if((c0 = T.get(--j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
SA[b++] = ((0 < j) && (T.get(j - 1) < c1)) ? ~j : j;
}
}
/* compute SAs */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, true); /* find ends of buckets */
for(i = n - 1, b = B.get(c1 = 0);0 <= i;--i){
if(0 < (j = SA[i])){
if((c0 = T.get(--j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
SA[--b] = ((j == 0) || (T.get(j - 1) > c1)) ? ~j : j;
}else{
SA[i] = ~j;
}
}
}
/*
* find the suffix array SA of T[0..n-1] in {0..k-1}^n use a working space
* (excluding T and SA) of at most 2n+O(1) for a constant alphabet
*/
private static void SA_IS(BaseArray T, int[] SA, int fs, int n, int k) {
BaseArray C, B, RA;
int i, j, b, m, p, q, name, newfs;
int c0, c1;
int flags = 0;
if(k <= 256){
C = new IntArray(new int[k], 0);
if(k <= fs){
B = new IntArray(SA, n + fs - k);
flags = 1;
}else{
B = new IntArray(new int[k], 0);
flags = 3;
}
}else if(k <= fs){
C = new IntArray(SA, n + fs - k);
if(k <= (fs - k)){
B = new IntArray(SA, n + fs - k * 2);
flags = 0;
}else if(k <= 1024){
B = new IntArray(new int[k], 0);
flags = 2;
}else{
B = C;
flags = 8;
}
}else{
C = B = new IntArray(new int[k], 0);
flags = 4 | 8;
}
/*
* stage 1: reduce the problem by at least 1/2 sort all the
* LMS-substrings
*/
getCounts(T, C, n, k);
getBuckets(C, B, k, true); /* find ends of buckets */
for(i = 0;i < n;++i){
SA[i] = 0;
}
b = -1;
i = n - 1;
j = n;
m = 0;
c0 = T.get(n - 1);
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
for(;0 <= i;){
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
if(0 <= i){
if(0 <= b){
SA[b] = j;
}
b = B.update(c1, -1);
j = i;
++m;
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
}
}
if(1 < m){
LMSsort(T, SA, C, B, n, k);
name = LMSpostproc(T, SA, n, m);
}else if(m == 1){
SA[b] = j + 1;
name = 1;
}else{
name = 0;
}
/*
* stage 2: solve the reduced problem recurse if names are not yet
* unique
*/
if(name < m){
if((flags & 4) != 0){
C = null;
B = null;
}
if((flags & 2) != 0){
B = null;
}
newfs = (n + fs) - (m * 2);
if((flags & (1 | 4 | 8)) == 0){
if((k + name) <= newfs){
newfs -= k;
}else{
flags |= 8;
}
}
for(i = m + (n >> 1) - 1, j = m * 2 + newfs - 1;m <= i;--i){
if(SA[i] != 0){
SA[j--] = SA[i] - 1;
}
}
RA = new IntArray(SA, m + newfs);
SA_IS(RA, SA, newfs, m, name);
RA = null;
i = n - 1;
j = m * 2 - 1;
c0 = T.get(n - 1);
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
for(;0 <= i;){
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
if(0 <= i){
SA[j--] = i + 1;
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
}
}
for(i = 0;i < m;++i){
SA[i] = SA[m + SA[i]];
}
if((flags & 4) != 0){
C = B = new IntArray(new int[k], 0);
}
if((flags & 2) != 0){
B = new IntArray(new int[k], 0);
}
}
/* stage 3: induce the result for the original problem */
if((flags & 8) != 0){
getCounts(T, C, n, k);
}
/* put all left-most S characters into their buckets */
if(1 < m){
getBuckets(C, B, k, true); /* find ends of buckets */
i = m - 1;
j = n;
p = SA[m - 1];
c1 = T.get(p);
do{
q = B.get(c0 = c1);
while (q < j){
SA[--j] = 0;
}
do{
SA[--j] = p;
if(--i < 0){
break;
}
p = SA[i];
}while ((c1 = T.get(p)) == c0);
}while (0 <= i);
while (0 < j){
SA[--j] = 0;
}
}
induceSA(T, SA, C, B, n, k);
C = null;
B = null;
}
/* char */
public static void suffixsort(char[] T, int[] SA, int n) {
if((T == null) || (SA == null) || (T.length < n) || (SA.length < n)){
return;
}
if(n <= 1){
if(n == 1){
SA[0] = 0;
}
return;
}
SA_IS(new CharArray(T, 0), SA, 0, n, 128);
}
public static int[] sa(char[] T)
{
int n = T.length;
int[] sa = new int[n];
suffixsort(T, sa, n);
return sa;
}
public static int[] buildLCP(char[] str, int[] sa)
{
int n = str.length;
int h = 0;
int[] lcp = new int[n];
int[] isa = new int[n];
for(int i = 0;i < n;i++)isa[sa[i]] = i;
for(int i = 0;i < n;i++){
if(isa[i] > 0){
for(int j = sa[isa[i]-1]; j+h<n && i+h<n && str[j+h] == str[i+h]; h++);
lcp[isa[i]] = h;
}else{
lcp[isa[i]] = 0;
}
if(h > 0)h--;
}
return lcp;
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new G().run(); }
private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
Python 3 Similar Strings HackerRank Solution
def is_similar(string1,string2):
dictionary = {}
for x in range(len(string1)):
try:
if dictionary[string1[x]]:
pass
except:
if string2[x] in dictionary.values():
return False
dictionary[string1[x]] = string2[x]
if not dictionary[string1[x]]==string2[x]:
return False
return True
n,q = list(int(x) for x in input().split())
string = input().strip()
for x in range(q):
start,end = list(int(x) for x in input().split())
string_check = string[start-1:end]
answer = 0
for y in range(n-end+start):
#print(string[y:y+end-start+1])
if is_similar(string_check,string[y:y+end-start+1]):
answer+=1
print(answer)
Python 2 Similar Strings HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
l, n = map(int, raw_input().strip().split())
z = raw_input().strip()
s = []
for x in z:
s.append(x)
for _ in xrange(n):
i, j = map(int, raw_input().strip().split())
a = dict()
e = []
for k, x in enumerate(s[i-1 : j]):
if not a.has_key(x):
a[x] = k
e.append(a[x])
le = j - i
ret = 0
for g, y in enumerate(s[:(len(s) - le)]):
a = dict()
for k, x in enumerate(s[g : g + le + 1]):
if not a.has_key(x):
a[x] = k
if e[k] != a[x]:
break
else:
ret += 1
print ret
C Similar Strings HackerRank Solution
#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;
}
Comments 1