• Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
Friday, January 27, 2023
  • Login
Zeroplusfour
No Result
View All Result
  • Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
  • Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
No Result
View All Result
Zeroplusfour
No Result
View All Result
Home Updates

Pseudo-Isomorphic Substrings – HackerRank Solution

Pseudo-Isomorphic Substrings - HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

bhautik bhalala by bhautik bhalala
May 24, 2022
Reading Time: 7 mins read
0
15 Days to learn SQL Hard SQL(Advanced)-Solution

15 Days to learn SQL Hard SQL(Advanced)-Solution alt text

Spread the love

Table of Contents

  • Pseudo-Isomorphic Substrings – 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++ Pseudo-Isomorphic Substrings HackerRank Solution
    • C++ Pseudo-Isomorphic Substrings HackerRank Solution Approch 2 
  • Java Pseudo-Isomorphic Substrings HackerRank Solution
  • Python 3 Pseudo-Isomorphic Substrings HackerRank Solution
  • C Pseudo-Isomorphic Substrings HackerRank Solution
  • Pytho 2 Pseudo-Isomorphic Substrings HackerRank Solution
    • Leave a comment below
      • Related posts:

Pseudo-Isomorphic Substrings – 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++ Pseudo-Isomorphic Substrings HackerRank Solution


Copy Code Copied Use a different Browser

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define fo(i,a,b) dfo(int,i,a,b)
#define fr(i,n) dfr(int,i,n)
#define fe(i,a,b) dfe(int,i,a,b)
#define fq(i,n) dfq(int,i,n)
#define nfo(i,a,b) dfo(,i,a,b)
#define nfr(i,n) dfr(,i,n)
#define nfe(i,a,b) dfe(,i,a,b)
#define nfq(i,n) dfq(,i,n)
#define dfo(d,i,a,b) for (d i = (a); i < (b); i++)
#define dfr(d,i,n) dfo(d,i,0,n)
#define dfe(d,i,a,b) for (d i = (a); i <= (b); i++)
#define dfq(d,i,n) dfe(d,i,1,n)
#define ffo(i,a,b) dffo(int,i,a,b)
#define ffr(i,n) dffr(int,i,n)
#define ffe(i,a,b) dffe(int,i,a,b)
#define ffq(i,n) dffq(int,i,n)
#define nffo(i,a,b) dffo(,i,a,b)
#define nffr(i,n) dffr(,i,n)
#define nffe(i,a,b) dffe(,i,a,b)
#define nffq(i,n) dffq(,i,n)
#define dffo(d,i,a,b) for (d i = (b)-1; i >= (a); i--)
#define dffr(d,i,n) dffo(d,i,0,n)
#define dffe(d,i,a,b) for (d i = (b); i >= (a); i--)
#define dffq(d,i,n) dffe(d,i,1,n)
#define ll long long
#define alok(n,t) ((t*)malloc((n)*sizeof(t)))
#define pf printf
#define sf scanf
#define pln pf("\n")


#define inf 11111111
char *s = alok(100111, char);
char *t = s - 1;
int n, n1, n11;

#define base 3

int *pbase = alok(100111, int);
void init_bases() {
	*pbase = 1;
	fo(i,1,100111) {
		pbase[i] = pbase[i-1] * base;
	}
}
void init_hash(char *v, int *w, int n) {
	*w = 0;
	fr(i,n) w[i + 1] = w[i] + pbase[i] * v[i];
}

char *vs[26];
int *ws[26];
int *nex[26];

int *lf;
int *rg;
//int *stk;
int *ssi;

int *hs;
struct streng {
	int off;
	int ord[26];
	int iord[26];
};

streng *ss;

#define st_get(a,i) ((a).iord[s[i]])

#define cond1(a,b) (wa[aend] + nwa) * moff != (wb[bend] + nwb)
#define cond2(a,b) (wa[aend] + nwa) != (wb[bend] + nwb) * moff

#define do13(cmd) do {cmd(0);cmd(1);cmd(2);cmd(3);cmd(4);cmd(5);cmd(6);cmd(7);cmd(8);cmd(9);cmd(10);cmd(11);cmd(12);} while (0)
#define do26(cmd) do {cmd(0);cmd(1);cmd(2);cmd(3);cmd(4);cmd(5);cmd(6);cmd(7);cmd(8);cmd(9);cmd(10);cmd(11);cmd(12);cmd(13);cmd(14);cmd(15);cmd(16);cmd(17);cmd(18);cmd(19);cmd(20);cmd(21);cmd(22);cmd(23);cmd(24);cmd(25);} while (0)
#define do13ab(cmd,a,b) do {cmd(0,a,b);cmd(1,a,b);cmd(2,a,b);cmd(3,a,b);cmd(4,a,b);cmd(5,a,b);cmd(6,a,b);cmd(7,a,b);cmd(8,a,b);cmd(9,a,b);cmd(10,a,b);cmd(11,a,b);cmd(12,a,b);} while (0)
#define do26ab(cmd,a,b) do {cmd(0,a,b);cmd(1,a,b);cmd(2,a,b);cmd(3,a,b);cmd(4,a,b);cmd(5,a,b);cmd(6,a,b);cmd(7,a,b);cmd(8,a,b);cmd(9,a,b);cmd(10,a,b);cmd(11,a,b);cmd(12,a,b);cmd(13,a,b);cmd(14,a,b);cmd(15,a,b);cmd(16,a,b);cmd(17,a,b);cmd(18,a,b);cmd(19,a,b);cmd(20,a,b);cmd(21,a,b);cmd(22,a,b);cmd(23,a,b);cmd(24,a,b);cmd(25,a,b);} while (0)
#define do3abl(cmd,a,b,l) do {cmd(0,a,b,l);cmd(1,a,b,l);cmd(2,a,b,l);} while (0)
#define do13abl(cmd,a,b,l) do {cmd(0,a,b,l);cmd(1,a,b,l);cmd(2,a,b,l);cmd(3,a,b,l);cmd(4,a,b,l);cmd(5,a,b,l);cmd(6,a,b,l);cmd(7,a,b,l);cmd(8,a,b,l);cmd(9,a,b,l);cmd(10,a,b,l);cmd(11,a,b,l);cmd(12,a,b,l);} while (0)
#define do26abl(cmd,a,b,l) do {cmd(0,a,b,l);cmd(1,a,b,l);cmd(2,a,b,l);cmd(3,a,b,l);cmd(4,a,b,l);cmd(5,a,b,l);cmd(6,a,b,l);cmd(7,a,b,l);cmd(8,a,b,l);cmd(9,a,b,l);cmd(10,a,b,l);cmd(11,a,b,l);cmd(12,a,b,l);cmd(13,a,b,l);cmd(14,a,b,l);cmd(15,a,b,l);cmd(16,a,b,l);cmd(17,a,b,l);cmd(18,a,b,l);cmd(19,a,b,l);cmd(20,a,b,l);cmd(21,a,b,l);cmd(22,a,b,l);cmd(23,a,b,l);cmd(24,a,b,l);cmd(25,a,b,l);} while (0)
#define do39abl(cmd,a,b,l) do {cmd(0,a,b,l);cmd(1,a,b,l);cmd(2,a,b,l);cmd(3,a,b,l);cmd(4,a,b,l);cmd(5,a,b,l);cmd(6,a,b,l);cmd(7,a,b,l);cmd(8,a,b,l);cmd(9,a,b,l);cmd(10,a,b,l);cmd(11,a,b,l);cmd(12,a,b,l);cmd(13,a,b,l);cmd(14,a,b,l);cmd(15,a,b,l);cmd(16,a,b,l);cmd(17,a,b,l);cmd(18,a,b,l);cmd(19,a,b,l);cmd(20,a,b,l);cmd(21,a,b,l);cmd(22,a,b,l);cmd(23,a,b,l);cmd(24,a,b,l);cmd(25,a,b,l);cmd(26,a,b,l);cmd(27,a,b,l);cmd(28,a,b,l);cmd(29,a,b,l);cmd(30,a,b,l);cmd(31,a,b,l);cmd(32,a,b,l);cmd(33,a,b,l);cmd(34,a,b,l);cmd(35,a,b,l);cmd(36,a,b,l);cmd(37,a,b,l);cmd(38,a,b,l);} while (0)
#define do52abl(cmd,a,b,l) do {cmd(0,a,b,l);cmd(1,a,b,l);cmd(2,a,b,l);cmd(3,a,b,l);cmd(4,a,b,l);cmd(5,a,b,l);cmd(6,a,b,l);cmd(7,a,b,l);cmd(8,a,b,l);cmd(9,a,b,l);cmd(10,a,b,l);cmd(11,a,b,l);cmd(12,a,b,l);cmd(13,a,b,l);cmd(14,a,b,l);cmd(15,a,b,l);cmd(16,a,b,l);cmd(17,a,b,l);cmd(18,a,b,l);cmd(19,a,b,l);cmd(20,a,b,l);cmd(21,a,b,l);cmd(22,a,b,l);cmd(23,a,b,l);cmd(24,a,b,l);cmd(25,a,b,l);cmd(26,a,b,l);cmd(27,a,b,l);cmd(28,a,b,l);cmd(29,a,b,l);cmd(30,a,b,l);cmd(31,a,b,l);cmd(32,a,b,l);cmd(33,a,b,l);cmd(34,a,b,l);cmd(35,a,b,l);cmd(36,a,b,l);cmd(37,a,b,l);cmd(38,a,b,l);cmd(39,a,b,l);cmd(40,a,b,l);cmd(41,a,b,l);cmd(42,a,b,l);cmd(43,a,b,l);cmd(44,a,b,l);cmd(45,a,b,l);cmd(46,a,b,l);cmd(47,a,b,l);cmd(48,a,b,l);cmd(49,a,b,l);cmd(50,a,b,l);cmd(51,a,b,l);} while (0)
int *was[26];
int *wbs[26];
int nwas[26];
int nwbs[26];

#define atake1(cc,a,b,L) atake(cc,a,b,L,cond1)
#define atake2(cc,a,b,L) atake(cc,a,b,L,cond2)
#define atake(cc,a,b,L,cond) {\
	int M = nex[a.ord[cc]][a.off] + naoff;\
	int X = nex[b.ord[cc]][b.off] + nboff;\
	if (M > X) M = X;\
	if (M < R1) M++;\
	int aend = a.off + M;\
	int bend = b.off + M;\
	fe(d,(prm==M?cc:0),cc) {\
		int *wa = ws[a.ord[d]];\
		int *wb = ws[b.ord[d]];\
		int nwa = -wa[a.off];\
		int nwb = -wb[b.off];\
		if (cond(a,b)) {\
			was[bc] = wa;\
			wbs[bc] = wb;\
			nwas[bc] = nwa;\
			nwbs[bc++] = nwb;\
		}\
	}\
	if (bc) {\
		R = M;\
		break;\
	} else {\
		L = M;\
		if (M == R) break;\
	}\
	prm = M;\
}
#define atsuke(a,b,L,cond) {\
	int aend = a.off + M;\
	int bend = b.off + M;\
	if (gud = a.iord[t[aend]] == b.iord[t[bend]]) fr(ci,bc) {\
		int *wa = was[ci];\
		int *wb = wbs[ci];\
		int nwa = nwas[ci];\
		int nwb = nwbs[ci];\
		if (cond(a,b)) {\
			gud = 0;\
			break;\
		}\
	}\
	(gud ? L : R) = M;\
}
#define atsoke(it,a,b,L,cond) {\
	int M = L + 1;\
	atsuke(a,b,L,cond);\
	if(R==L+1) break;\
}
#define atsoke1(it,a,b,L) atsoke(it,a,b,L,cond1)
#define atsoke2(it,a,b,L) atsoke(it,a,b,L,cond2)
#define atshoke(it,a,b,L) {\
	int M = L + 1;\
	int aend = a.off + M;\
	int bend = b.off + M;\
	if (a.iord[t[aend]] != b.iord[t[bend]]) {\
		R = M;\
		break;\
	} else {\
		L = M;\
	}\
}

#define st_match(a,b,L) do {\
	int R = n1 - (a.off > b.off ? a.off : b.off);\
	int R1 = R-1;\
	int moff;\
	L = 0;\
	int prm = -1;\
	int gud;\
	int naoff = -a.off;\
	int nboff = -b.off;\
	int bc = 0;\
	if (a.off < b.off) {\
		moff = pbase[b.off - a.off];\
		do26abl(atake1,a,b,L);\
		do13abl(atshoke,a,b,L);\
		while (R > L + 16) {\
			int M = L + R >> 1;\
			atsuke(a,b,L,cond1);\
			M = L + R >> 1;\
			atsuke(a,b,L,cond1);\
			M = L + R >> 1;\
			atsuke(a,b,L,cond1);\
			M = L + R >> 1;\
			atsuke(a,b,L,cond1);\
		}\
		while (R > L + 1) {\
			int M = L + R >> 1;\
			atsuke(a,b,L,cond1);\
		}\
	} else {\
		moff = pbase[a.off - b.off];\
		do26abl(atake2,a,b,L);\
		do13abl(atshoke,a,b,L);\
		while (R > L + 16) {\
			int M = L + R >> 1;\
			atsuke(a,b,L,cond2);\
			M = L + R >> 1;\
			atsuke(a,b,L,cond2);\
			M = L + R >> 1;\
			atsuke(a,b,L,cond2);\
			M = L + R >> 1;\
			atsuke(a,b,L,cond2);\
		}\
		while (R > L + 1) {\
			int M = L + R >> 1;\
			atsuke(a,b,L,cond2);\
		}\
	}\
} while (0)

int st_comp(const void *aa, const void *bb) {
	streng a = ss[*(int*)aa];
	streng b = ss[*(int*)bb];
	int L;
	st_match(a,b,L);
	return st_get(a, L + a.off) - st_get(b, L + b.off);
}
char *add(char *s, ll v) {
	if (!v) return s;
	s = add(s, v / 10);
	*(s++) = v % 10 + '0';
	return s;
}
int main() {
	init_bases();
	sf("%s", s);
	n = strlen(s);
	n1 = n + 1;
	n11 = n + 11;
	fr(i,n) s[i] -= 'a';
	s[n] = -1;
	for (int i = 0, j = n - 1; i < j; i++, j--) {
		s[i] ^= s[j], s[j] ^= s[i], s[i] ^= s[j];
	}
	#define cvinit(c) {\
		vs[c]  = alok(n11, char);\
		ws[c]  = alok(n11, int);\
		nex[c] = alok(n11, int);\
		fr(i,n11) vs[c][i] = 0;\
	}
	do26(cvinit);
	fr(i,n) vs[s[i]][i] = 1;
	#define cnex(c) {\
		int pv = nex[c][n] = n;\
		ffr(i,n) pv = nex[c][i] = vs[c][i] ? i : pv;\
	}
	#define cinit(c) init_hash(vs[c], ws[c], n);
	do26(cnex);
	do26(cinit);
	ss = alok(n11, streng);
	hs = alok(n11, int);
	ss[0].off = hs[0] = 0;
	int *ord = alok(27, int) + 1;
	int *val = alok(27, int) + 1;
	fo(c,-1,26) ord[c] = c;
	val[-1] = ord[-1] = -1;
	fe(i,0,n) {
		ss[i].off = hs[i] = i;
		#define chval(c) val[c] = nex[c][i]*26+c;
		do26(chval);
		fr(j,26) {
			int tp = ord[j];
			int w = val[tp];
			int k;
			for (k = j-1; val[ord[k]] > w; k--) {
				ord[k+1] = ord[k];
			}
			ord[k+1] = tp;
		}
		#define cford(c) ss[i].ord[c] = ord[c];
		#define ciord(c) ss[i].iord[ord[c]] = c;
		do26(cford);
		do26(ciord);
	}

	qsort(hs, n1, sizeof(int), st_comp);

	lf = alok(n, int);
	rg = alok(n, int);
	#define stk ssi
	//ssi = alok(n11, int);
	stk = alok(n11, int);
	int stc = 0;
	*stk = n;
	fe(i,0,n) {
		int off = ss[hs[i]].off;
		while (stk[stc] < off) stc--;
		lf[off] = stk[stc];
		stk[++stc] = off;
	}
	stc = 0;
	ffe(i,0,n) {
		int off = ss[hs[i]].off;
		while (stk[stc] < off) stc--;
		rg[off] = stk[stc];
		stk[++stc] = off;
	}
	//ssi = alok(n11, int);
	fe(i,0,n) ssi[ss[i].off] = i;
	ll ans = 0;
	char *so = alok(26*n11, char);
	char *soo = so;
	ffr(i,n) {
		int mx = 0, my = 0;
		streng sl = ss[ssi[i]];
		streng sr1 = ss[ssi[lf[i]]];
		streng sr2 = ss[ssi[rg[i]]];
		if (lf[i] < n) st_match(sl, sr1, mx);
		if (rg[i] < n) st_match(sl, sr2, my);
		ans += n - i - (mx > my ? mx : my);
		so = add(so, ans);
		*(so++) = '\n';
		//**/pf("%lld\n", ans);
	}
	*(so++) = 0;
	pf(soo);
}

C++ Pseudo-Isomorphic Substrings HackerRank Solution Approch 2 


Copy Code Copied Use a different Browser

 

// https://www.hackerrank.com/challenges/pseudo-isomorphic-substrings
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

#define LOGMAX 17
#define NMAX 131072
#define DEBUG 0
#define USE_FILES 0

int qans, qmin, qmax, nactsuff, pmin, pmax, N;
long long cans, sumlcp, sumactsuff;
int bit[LOGMAX + 1], logidx[NMAX];
int rmq[2][NMAX][LOGMAX], lcp[NMAX];
char S[NMAX];

void compute_bits() {
	int i, j;
	bit[0] = 1;

	for (i = 1; i <= LOGMAX; i++)
		bit[i] = bit[i - 1] << 1;

	logidx[1] = 0;

	for (i = 2, j = 1; i < NMAX; i++) {
		if (i == bit[j + 1]) j++;
		logidx[i] = j;
	}
}

void pre_compute_RMQ() {
	int i, j;

	for (i = 1; i < N; i++) {
		rmq[0][i][0] = rmq[1][i][0] = lcp[i];

		for (j = 1; j < LOGMAX && i - bit[j] >= 0; j++) {
			rmq[0][i][j] = rmq[0][i - bit[j - 1]][j - 1];

			if (rmq[0][i][j - 1] < rmq[0][i][j])
				rmq[0][i][j] = rmq[0][i][j - 1];
		}
	}

	for (i = N - 1; i >= 1; i--) {
		for (j = 1; j < LOGMAX && i + bit[j] <= N; j++) {
			rmq[1][i][j] = rmq[1][i + bit[j - 1]][j - 1];

			if (rmq[1][i][j - 1] < rmq[1][i][j])
				rmq[1][i][j] = rmq[1][i][j - 1];
		}
	}
}

void get_query() {
	int idx = logidx[qmax - qmin + 1];
	qans = rmq[0][qmax][idx];
	if (rmq[1][qmin][idx] < qans)
		qans = rmq[1][qmin][idx];
}

void read_input() {
	if (USE_FILES)
		freopen("x.txt", "r", stdin);
	scanf("%s", S + 1);
	N = strlen(S + 1);
}

void reverse_S() {
	int i;
	char c;
	for (i = 1; i <= N / 2; i++) {
		c = S[i];
		S[i] = S[N - i + 1];
		S[N - i + 1] = c;
	}
}

int D[NMAX];
map<char, int> lastpoz, nextpoz;
map<char, int>::iterator it;
vector<int> out[NMAX];
vector<pair<int, char> > vpoz;
int cidx[NMAX][30];

void pre_process_str() {
	int i, j, k;

	for (i = 1; i <= N; i++) {
		D[i] = i - lastpoz[S[i]];
		lastpoz[S[i]] = i;

		for (j = i - D[i] + 1; j <= i; j++)
			out[j].push_back(i);
	}

	if (DEBUG) {
		fprintf(stderr, "D:");

		for (i = 1; i <= N; i++)
			fprintf(stderr, " %d", D[i]);

		fprintf(stderr, "\n");
	}

	char ch;

	for (ch = 'a'; ch <= 'z'; ch++)
		nextpoz[ch] = N + 1;

	for (i = N; i >= 1; i--) {
		nextpoz[S[i]] = i;
		vpoz.clear();

		for (it = nextpoz.begin(); it != nextpoz.end(); it++)
			vpoz.push_back(make_pair(it->second, it->first));
		sort(vpoz.begin(), vpoz.end());

		for (j = 0; j < vpoz.size(); j++)
			cidx[i][vpoz[j].second - 'a'] = j;
	}
}

int group[LOGMAX + 1][NMAX], vs[NMAX], vsrev[NMAX], vsaux[NMAX], r, ii, jj, kk;

int LCP(int s1, int s2) {
	if (group[r][s1] == group[r][s2]) {
		int p = s1 + bit[r], q = s2 + bit[r], lenmax, u, poz;

		if (p > N || q > N) return bit[r];

		if (group[r][p] != group[r][q]) {
			qmin = min(vsrev[p], vsrev[q]);
			qmax = max(vsrev[p], vsrev[q]) - 1;
			get_query();
			lenmax = bit[r] + qans;
		} else
			lenmax = bit[r + 1];

		for (u = 0; u < out[p].size(); u++) {
			poz = out[p][u];

			if (poz - s1 >= lenmax) break;

			if (poz - D[poz] >= s1 && D[poz - s1 + s2] != D[poz]) {
				lenmax = poz - s1;
				break;
			}
		}

		for (u = 0; u < out[q].size(); u++) {
			poz = out[q][u];

			if (poz - s2 >= lenmax) break;

			if (poz - D[poz] >= s2 && D[poz - s2 + s1] != D[poz]) {
				lenmax = poz - s2;
				break;
			}
		}

		return lenmax;
	} else {
		qmin = min(vsrev[s1], vsrev[s2]);
		qmax = max(vsrev[s1], vsrev[s2]) - 1;
		get_query();
		return qans;
	}
}

void compute_LCPs() {
	int i, j, p, q, lenmax, u, poz;

	for (i = 1; i < N; i++)
		lcp[i] = LCP(vs[i], vs[i + 1]);

	if (DEBUG)
		for (i = 1; i < N; i++)
			fprintf(stderr, "i=%d: LCP(%d,%d)=%d\n", i, vs[i], vs[i + 1], lcp[i]);
}

int d1, d2, clcp;

inline int compare_suffixes(int s1, int s2) {
	clcp = LCP(s1, s2);
	d1 = s1 + clcp;
	d2 = s2 + clcp;

	if (d1 > N) return +1;
	if (d2 > N) return -1;
	return (cidx[s1][S[d1] - 'a'] - cidx[s2][S[d2] - 'a']);
}

void merge_sort(int li, int ls) {
	if (li >= ls) return;

	int mid = (li + ls) >> 1;

	merge_sort(li, mid);
	merge_sort(mid + 1, ls);

	ii = li; jj = mid + 1; kk = li - 1;

	while (ii <= mid && jj <= ls) {
		kk++;

		if (compare_suffixes(vs[ii], vs[jj]) <= 0) {
			vsaux[kk] = vs[ii];
			ii++;
		} else {
			vsaux[kk] = vs[jj];
			jj++;
		}
	}

	for (; ii <= mid; ii++) {
		kk++;
		vsaux[kk] = vs[ii];
	}

	for (; jj <= ls; jj++) {
		kk++;
		vsaux[kk] = vs[jj];
	}

	for (kk = li; kk <= ls; kk++)
		vs[kk] = vsaux[kk];
}

void suffix_array() {
	int i, j, ng = 1;

	for (i = 1; i <= N; i++) {
		vs[i] = i;
		vsrev[i] = i;
		lcp[i] = 1;
		group[0][i] = 0;
	}

	for (r = 0; r < LOGMAX; r++) {
		pre_compute_RMQ();
		merge_sort(1, N);

		ng = 0;
		group[r + 1][vs[1]] = 0;

		compute_LCPs();
		for (i = 2; i <= N; i++) {
			if (lcp[i - 1] != bit[r + 1])
				ng++;
			group[r + 1][vs[i]] = ng;
		}

		ng++;

		for (i = 1; i <= N; i++)
			vsrev[vs[i]] = i;

		if (DEBUG) {
			fprintf(stderr, "Suffix array after round %d/%d:", r + 1, LOGMAX);
			for (i = 1; i <= N; i++)
				fprintf(stderr, " %d(%d)", vs[i], group[r + 1][vs[i]]);
			fprintf(stderr, "\n");
		}
	}
}

int cnt[2 * NMAX];

void UpdateCnt(int idx, int v) {
	sumactsuff += v * vs[idx];
	nactsuff += v;
	idx = NMAX + idx - 1;
	while (idx >= 1) {
		cnt[idx] += v;
		idx >>= 1;
	}
}

int GetPred(int idx) {
	idx = NMAX + idx - 1;
	int p;
	while (idx > 1) {
		p = idx >> 1;
		if ((idx & 1) == 1 && cnt[p] > cnt[idx]) {
			idx--;
			break;
		}
		idx = p;
	}

	if (idx == 1)
		return 0;

	while (idx < NMAX) {
		idx <<= 1;
		if (cnt[idx + 1] >= 1)
			idx++;
	}

	return idx - NMAX + 1;
}

int GetSucc(int idx) {
	idx = NMAX + idx - 1;
	int p;
	while (idx > 1) {
		p = idx >> 1;
		if ((idx & 1) == 0 && cnt[p] > cnt[idx]) {
			idx++;
			break;
		}
		idx = p;
	}

	if (idx == 1)
		return 0;

	while (idx < NMAX) {
		idx <<= 1;
		if (cnt[idx] == 0)
			idx++;
	}

	return idx - NMAX + 1;
}

#define QSIZE 10000000

int qactsuff[QSIZE], nextqactsuff[QSIZE], startactsuff[NMAX], nq;
int idxmax[NMAX];

int update_LCPPairState(int s1, int s2, int coef) {
	int idx, result = 2;
	qmin = s1; qmax = s2 - 1;
	get_query();

	if (qans == 0)
		return 0;

	s1 = vs[s1]; s2 = vs[s2];
	if (s1 > s2) {
		idx = s1; s1 = s2; s2 = idx;
		result = 1;
	}

	idx = s2 + qans - 1;
	if (idx > pmax)
		return result;

	sumlcp += coef * qans;
	if (coef == 1) {
		if (result == 2)
			qmin = qmax + 1;
		if (idx > idxmax[qmin]) {
			nq++;
			if (nq >= QSIZE) {
				fprintf(stderr, "!! QSIZE exceeded\n");
				exit(1);
			}
			qactsuff[nq] = qmin;
			nextqactsuff[nq] = startactsuff[idx];
			startactsuff[idx] = nq;
			idxmax[qmin] = idx;
		}
	}
	return 0;
}

void update_state(int s, int coef) {
	int pred, succ, p, res, removed;

	pred = GetPred(s);
	succ = GetSucc(s);

	if (DEBUG)
		fprintf(stderr, "  suffix: s=%d pred=%d succ=%d\n", s, pred, succ);

	if (pred > 0 && succ > 0)
		update_LCPPairState(pred, succ, -1);

	removed = 0;
	while (pred > 0) {
		res = update_LCPPairState(pred, s, 1);
		if (!res)
			break;
		if (res == 1) {
			UpdateCnt(pred, -1);
			p = GetPred(pred);
			if (p > 0)
				update_LCPPairState(p, pred, -1);
			pred = p;
		} else {
			removed = 1;
			break;
		}
	}

	if (!removed) {
		while (succ > 0) {
			res = update_LCPPairState(s, succ, coef);
			if (!res)
				break;
			if (res == 2) {
				UpdateCnt(succ, -1);
				p = GetSucc(succ);
				if (p > 0)
					update_LCPPairState(succ, p, -1);
				succ = p;
			} else {
				removed = 1;
				break;
			}
		}
	}

	if (removed) {
		pred = GetPred(s);
		succ = GetSucc(s);
		if (pred > 0 && succ > 0)
			update_LCPPairState(pred, succ, 1);
	}
}

void process_op() {
	int opidx;

	sumlcp = sumactsuff = 0;
	nactsuff = 0;
	pmin = N + 1;
	pmax = N;

	for (opidx = 1; opidx <= N; opidx++) {
		pmin--;
		UpdateCnt(vsrev[pmin], 1);
		update_state(vsrev[pmin], 1);
		cans = (long long) (pmax + 1) * (long long) nactsuff;
		cans -= sumactsuff;
		cans -= sumlcp;
		if (DEBUG)
			fprintf(stderr, "op=%d pmin=%d suff=%d cans=%lld pmax=%d nactsuff=%d sumactsuff=%lld sumlcp=%lld\n", opidx, pmin, vsrev[pmin], cans, pmax, nactsuff, sumactsuff, sumlcp);
		printf("%lld\n", cans);
	}
}

int main() {
	compute_bits();
	read_input();
	reverse_S();
	pre_process_str();
	suffix_array();
	pre_compute_RMQ();
	process_op();
	return 0;
}

 

Java Pseudo-Isomorphic Substrings HackerRank Solution


Copy Code Copied Use a different Browser

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Locale;
import java.util.Map;
import java.util.NavigableSet;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Solution implements Runnable {
	static Random RND = new Random(7777L);
	static int MAX_LENGTH = 100000;
	static int ALPHA_SIZE = 26;
	static int HASH_BASE = BigInteger.probablePrime(17, RND).intValue();
	static int[] HASH_BASE_POWS = new int[MAX_LENGTH * 2];

	static {
		HASH_BASE_POWS[0] = 1;

		for (int i = 1; i < HASH_BASE_POWS.length; i++) {
			HASH_BASE_POWS[i] = HASH_BASE_POWS[i - 1] * HASH_BASE;
		}
	}

	char[] s;
	int length;
	int[][] charMaps;
	int[][] charPerms;
	int[][] distributedHashes;
	int[] hashPrefixes;
	Map<Long, Integer> lcpCache = new HashMap<Long, Integer>();

	void solve() throws IOException {
		s = new StringBuilder(in.readLine()).reverse().toString().toCharArray();
		length = s.length;
		charMaps = getCharMaps(s);
		charPerms = getCharPermutations(charMaps);
		distributedHashes = getDistributedHashes(s);
		hashPrefixes = precalcHashPrefixes(charPerms, distributedHashes);
		Integer[] suffixArray = getSuffixArray();
		final int[] suffixIndex = new int[length];

		for (int i = 0; i < length; i++) {
			suffixIndex[suffixArray[i]] = i;
		}

		NavigableSet<Integer> viewedSuffixes = new TreeSet<Integer>(
				new Comparator<Integer>() {
					@Override
					public int compare(Integer pos1, Integer pos2) {
						return suffixIndex[pos1] - suffixIndex[pos2];
					}
				});

		long[] counts = new long[length + 1];

		for (int pos = length - 1; pos >= 0; pos--) {
			long intersectionSize = 0L;

			{
				Integer neigbourPos = viewedSuffixes.lower(pos);

				if (neigbourPos != null) {
					intersectionSize = Math.max(intersectionSize,
							lcp(pos, neigbourPos));
				}
			}

			{
				Integer neigbourPos = viewedSuffixes.higher(pos);

				if (neigbourPos != null) {
					intersectionSize = Math.max(intersectionSize,
							lcp(pos, neigbourPos));
				}
			}

			counts[pos] = counts[pos + 1] + length - pos - intersectionSize;
			viewedSuffixes.add(pos);
		}

		for (int i = 0; i < length; i++) {
			out.println(counts[length - 1 - i]);
		}
	}

	Integer[] getSuffixArray() {
		Integer[] suffixArray = new Integer[length];

		for (int i = 0; i < length; i++) {
			suffixArray[i] = i;
		}

		Arrays.sort(suffixArray, new Comparator<Integer>() {
			@Override
			public int compare(Integer pos1, Integer pos2) {
				if (pos1.equals(pos2)) {
					return 0;
				}

				int lcp = lcp(pos1, pos2);

				if (lcp == length - pos1) {
					return -1;
				}

				if (lcp == length - pos2) {
					return +1;
				}

				return charMaps[pos1][s[pos1 + lcp] - 'a']
						- charMaps[pos2][s[pos2 + lcp] - 'a'];
			}
		});

		return suffixArray;
	}

	int lcp(int pos1, int pos2) {
		if (pos1 > pos2) {
			return lcp(pos2, pos1);
		}

		int leftBound = 0;
		int rightBound = length - pos2;
		int lcp = naiveLcp(pos1, pos2, Math.min(120, rightBound));

		if (lcp == -1) {
			leftBound = Math.min(15, rightBound);

			while (leftBound <= rightBound) {
				int middlePoint = (leftBound + rightBound) >> 1;

			if (equals(pos1, pos2, middlePoint)) {
				lcp = Math.max(lcp, middlePoint);
				leftBound = middlePoint + 1;
			} else {
				rightBound = middlePoint - 1;
			}
			}
		}

		return lcp;
	}

	int naiveLcp(int pos1, int pos2, int len) {
		int[] map1 = charMaps[pos1];
		int[] map2 = charMaps[pos2];

		for (int i = 0; i < len; i++) {
			if (map1[s[pos1 + i] - 'a'] != map2[s[pos2 + i] - 'a']) {
				return i;
			}
		}

		return -1;
	}

	boolean equals(int pos1, int pos2, int length) {
		if (pos1 > pos2) {
			return equals(pos2, pos1, length);
		}

		int hash1 = hash(pos1, length);
		int hash2 = hash(pos2, length);
		int hashAlingmentPower = HASH_BASE_POWS[pos2 - pos1];

		return hashAlingmentPower * hash1 == hash2;
	}

	int hash(int pos, int length) {
		int[] perm = charPerms[pos];
		int[] hashes = distributedHashes[pos + length];
		int hash = -hashPrefixes[pos];

		for (int rank = 0; rank < perm.length; rank++) {
			hash += hashes[perm[rank]] * rank;
		}

		return hash;
	}

	static int[][] getCharMaps(char[] s) {
		int length = s.length;
		int[][] linksToNext = getLinksToNext(s);
		int[][] maps = new int[length][ALPHA_SIZE];

		for (int offset = 0; offset < length; offset++) {
			int[] map = maps[offset];
			Arrays.fill(map, -1);
			int mapped = 0;
			map[s[offset] - 'a'] = mapped++;

			for (int pos = offset; pos < length;) {
				int nextPos = length;
				int nextChar = -1;

				for (int ch = 0; ch < ALPHA_SIZE; ch++) {
					if (map[ch] == -1) {
						if (nextPos > linksToNext[pos][ch]) {
							nextPos = linksToNext[pos][ch];
							nextChar = ch;
						}
					}
				}

				if (nextChar == -1) {
					break;
				}

				map[nextChar] = mapped++;
				pos = nextPos;
			}
		}

		return maps;
	}

	static int[][] getLinksToNext(char[] s) {
		int length = s.length;
		int[][] linksToNext = new int[length][ALPHA_SIZE];

		for (int[] row : linksToNext) {
			Arrays.fill(row, length);
		}

		for (int i = length - 2; i >= 0; i--) {
			System.arraycopy(linksToNext[i + 1], 0, linksToNext[i], 0,
					ALPHA_SIZE);
			linksToNext[i][s[i + 1] - 'a'] = i + 1;
		}

		return linksToNext;
	}

	static int[][] getDistributedHashes(char[] s) {
		int length = s.length;
		int[][] distributedHashes = new int[length + 1][ALPHA_SIZE];

		for (int i = 0; i < length; i++) {
			System.arraycopy(distributedHashes[i], 0, distributedHashes[i + 1],
					0, ALPHA_SIZE);
			distributedHashes[i + 1][s[i] - 'a'] += HASH_BASE_POWS[i];
		}

		return distributedHashes;
	}

	static int[][] getCharPermutations(int[][] charMaps) {
		int lenght = charMaps.length;
		int[][] charPerms = new int[lenght][];

		for (int pos = 0; pos < lenght; pos++) {
			charPerms[pos] = getCharPermutation(charMaps[pos]);
		}

		return charPerms;
	}

	static int[] getCharPermutation(int[] map) {
		int[] permutation = new int[ALPHA_SIZE];
		int last = 0;

		for (int ch = 0; ch < ALPHA_SIZE; ch++) {
			if (map[ch] != -1) {
				permutation[map[ch]] = ch;
				last = Math.max(last, map[ch]);
			}
		}

		return Arrays.copyOf(permutation, last + 1);
	}

	static int[] precalcHashPrefixes(int[][] charPerms,
			int[][] distributedHashes) {
		int length = charPerms.length;
		int[] hashPreffixes = new int[length];

		for (int pos = 0; pos < length; pos++) {
			int[] hashes = distributedHashes[pos];
			int[] perm = charPerms[pos];

			for (int rank = 0; rank < charPerms[pos].length; rank++) {
				hashPreffixes[pos] += hashes[perm[rank]] * rank;
			}
		}

		return hashPreffixes;
	}

	static Solution INSTANCE = new Solution();
	static boolean WRITE_LOG = true;
	static long STACK_SIZE = -1;

	public static void main(String[] args) throws IOException {
		try {
			if (STACK_SIZE < 0L) {
				INSTANCE.run();
			} else {
				new Thread(null, INSTANCE, "Solver", 1L << 24).start();
			}
		} catch (Throwable e) {
			e.printStackTrace();
			System.exit(999);
		}
	}

	@Override
	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			solve();
			out.close();
			in.close();
		} catch (Throwable e) {
			e.printStackTrace();
			System.exit(999);
		}
	}

	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");

	String nextToken() throws IOException {
		while (!st.hasMoreTokens()) {
			st = new StringTokenizer(in.readLine());
		}

		return st.nextToken();
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	int[] nextIntArray(int size) throws IOException {
		int[] ret = new int[size];

		for (int i = 0; i < size; i++) {
			ret[i] = nextInt();
		}

		return ret;
	}

	long[] nextLongArray(int size) throws IOException {
		long[] ret = new long[size];

		for (int i = 0; i < size; i++) {
			ret[i] = nextLong();
		}

		return ret;
	}

	double[] nextDoubleArray(int size) throws IOException {
		double[] ret = new double[size];

		for (int i = 0; i < size; i++) {
			ret[i] = nextDouble();
		}

		return ret;
	}

	String nextLine() throws IOException {
		st = new StringTokenizer("");

		return in.readLine();
	}

	boolean isEof() throws IOException {
		while (!st.hasMoreTokens()) {
			String s = in.readLine();

			if (s == null) {
				return true;
			}

			st = new StringTokenizer(s);
		}

		return false;
	}

	void printRepeat(String s, int count) {
		for (int i = 0; i < count; i++) {
			out.print(s);
		}
	}

	void printArray(int[] array) {
		if (array == null || array.length == 0) {
			return;
		}

		for (int i = 0; i < array.length; i++) {
			if (i > 0) {
				out.print(' ');
			}

			out.print(array[i]);
		}

		out.println();
	}

	void printArray(long[] array) {
		if (array == null || array.length == 0) {
			return;
		}

		for (int i = 0; i < array.length; i++) {
			if (i > 0) {
				out.print(' ');
			}

			out.print(array[i]);
		}

		out.println();
	}

	void printArray(double[] array) {
		if (array == null || array.length == 0) {
			return;
		}

		for (int i = 0; i < array.length; i++) {
			if (i > 0) {
				out.print(' ');
			}

			out.print(array[i]);
		}

		out.println();
	}

	void printArray(double[] array, String spec) {
		if (array == null || array.length == 0) {
			return;
		}

		for (int i = 0; i < array.length; i++) {
			if (i > 0) {
				out.print(' ');
			}

			out.printf(Locale.US, spec, array[i]);
		}

		out.println();
	}

	void printArray(Object[] array) {
		if (array == null || array.length == 0) {
			return;
		}

		boolean blank = false;

		for (Object x : array) {
			if (blank) {
				out.print(' ');
			} else {
				blank = true;
			}

			out.print(x);
		}

		out.println();
	}

	@SuppressWarnings("rawtypes")
	void printCollection(Collection collection) {
		if (collection == null || collection.isEmpty()) {
			return;
		}

		boolean blank = false;

		for (Object x : collection) {
			if (blank) {
				out.print(' ');
			} else {
				blank = true;
			}

			out.print(x);
		}

		out.println();
	}

	static void swap(int[] a, int i, int j) {
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

	static void swap(long[] a, int i, int j) {
		long tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

	static void swap(double[] a, int i, int j) {
		double tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

	static void shuffle(int[] a, int from, int to) {
		for (int i = from; i < to; i++) {
			swap(a, i, RND.nextInt(a.length));
		}
	}

	static void shuffle(long[] a, int from, int to) {
		for (int i = from; i < to; i++) {
			swap(a, i, RND.nextInt(a.length));
		}
	}

	static void shuffle(double[] a, int from, int to) {
		for (int i = from; i < to; i++) {
			swap(a, i, RND.nextInt(a.length));
		}
	}

	static void shuffle(int[] a) {
		if (a == null) {
			return;
		}

		shuffle(a, 0, a.length);
	}

	static void shuffle(long[] a) {
		if (a == null) {
			return;
		}

		shuffle(a, 0, a.length);
	}

	static void shuffle(double[] a) {
		if (a == null) {
			return;
		}

		shuffle(a, 0, a.length);
	}

	static long[] getPartialSums(int[] a) {
		long[] sums = new long[a.length + 1];

		for (int i = 0; i < a.length; i++) {
			sums[i + 1] = sums[i] + a[i];
		}

		return sums;
	}

	static long[] getPartialSums(long[] a) {
		long[] sums = new long[a.length + 1];

		for (int i = 0; i < a.length; i++) {
			sums[i + 1] = sums[i] + a[i];
		}

		return sums;
	}

	static int[] getOrderedSet(int[] a) {
		int[] set = Arrays.copyOf(a, a.length);

		if (a.length == 0) {
			return set;
		}

		shuffle(set);
		Arrays.sort(set);
		int k = 1;
		int prev = set[0];

		for (int i = 1; i < a.length; i++) {
			if (prev != set[i]) {
				set[k++] = prev = set[i];
			}
		}

		return Arrays.copyOf(set, k);
	}

	static long[] getOrderedSet(long[] a) {
		long[] set = Arrays.copyOf(a, a.length);

		if (a.length == 0) {
			return set;
		}

		shuffle(set);
		Arrays.sort(set);
		int k = 1;
		long prev = set[0];

		for (int i = 1; i < a.length; i++) {
			if (prev != set[i]) {
				set[k++] = prev = set[i];
			}
		}

		return Arrays.copyOf(set, k);
	}

	static int gcd(int x, int y) {
		x = Math.abs(x);
		y = Math.abs(y);

		while (x > 0 && y > 0) {
			if (x > y) {
				x %= y;
			} else {
				y %= x;
			}
		}

		return x + y;
	}

	static long gcd(long x, long y) {
		x = Math.abs(x);
		y = Math.abs(y);

		while (x > 0 && y > 0) {
			if (x > y) {
				x %= y;
			} else {
				y %= x;
			}
		}

		return x + y;
	}
}

 

Python 3 Pseudo-Isomorphic Substrings HackerRank Solution


Copy Code Copied Use a different Browser

s = input()

prevs = dict()
a = []
for i in range(len(s)):
    if s[i] in prevs:
        a.append(i - prevs[s[i]])
    else:
        a.append(i + 1)
    prevs[s[i]] = i

class Node:
    def __init__(self, **d):
        self.__dict__ = d

class Edge:
    def __init__(self, **d):
        self.__dict__ = d

root = Node(edges = dict(), depth = 0, slink = None)
edge0 = Edge(a = root, b = root, u = 0, l = 0)
cur = (edge0, 0, 0)
leaves = 0
ans = 0

def conv(c, depth):
    return -1 if c > depth else c

def simplify(cur):
    edge, u, l = cur
    while l > edge.l:
        c = conv(a[u + edge.l], edge.a.depth + edge.l)
        edge, u, l = edge.b.edges[c], u + edge.l, l - edge.l
    return edge, u, l

def toStr(a, depth):
    l = []
    for i in range(len(a)):
        l.append(conv(a[i], depth + i))
    return map(str, l)

def printTree(edge, tabs = ''):
    print(tabs + ':'.join(toStr(a[edge.u:edge.u+edge.l], edge.a.depth)), edge.b.depth, edge.b.slink)
    for e in edge.b.edges.values():
        printTree(e, tabs + '  ')

def slink(cur):
    edge, u, l = cur
    if edge.a == root:
        assert(edge != edge0)
        return simplify((edge0, u + 1, l - 1))
    else:
        edge.a.slink = simplify(edge.a.slink)
        e1, u1, l1 = edge.a.slink
        return simplify((e1, u - l1, l + l1))

#print(':'.join(map(str, a)))

for i in range(len(s)):
    while True:
        edge, u, l = cur
        c = conv(a[i], edge.a.depth + l)
        if l == edge.l:
            if c in edge.b.edges:
                break
            leaves += 1
            leaf = Node(depth = -1, slink = None, edges = dict())
            edge.b.edges[c] = Edge(a = edge.b, b = leaf, u = i, l = len(s) - i)
        else:
            c1 = conv(a[edge.u + l], edge.a.depth + l)
            if c == c1:
                break
            leaves += 1
            leaf = Node(depth = -1, slink = None, edges = dict())
            branch = Node(edges = dict(), depth = edge.a.depth + l, slink = slink(cur))
            branch.edges[c] = Edge(a = branch, b = leaf, u = i, l = len(s) - i)
            branch.edges[c1] = Edge(a = branch, b = edge.b, u = edge.u + l, l = edge.l - l)
            edge.b = branch
            edge.l = l
        if edge == edge0 and l == 0:
            cur = None
            break
        if edge.a == root:
            assert(edge != edge0)
            cur = simplify((edge0, u + 1, l - 1))
        else:
            edge.a.slink = simplify(edge.a.slink)
            e1, u1, l1 = edge.a.slink
            cur = simplify((e1, u - l1, l + l1))
    if cur == None:
        cur = edge0, i + 1, 0
    else:
        edge, u, l = cur
        assert(u + l == i)
        cur = simplify((edge, u, l + 1))
    ans += leaves
    print(ans)
    #printTree(edge0)

C Pseudo-Isomorphic Substrings HackerRank Solution


Copy Code Copied Use a different Browser

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>


#define min(a,b) (a > b ? b : a)
#define max(a,b) (a < b ? b : a)
#define DEBUG 1

#define print(...) \
    do { if (DEBUG) printf(__VA_ARGS__); } while(0)

char *str;
int strLen;
int **rankArr;
int *parent;
int currBlockInd;
int **prevPosArr;
int **nextPosArr;
int maxBlockCount;


int find (int *parent, int parentLen, int a)
{
    while (a != parent[a])
    {
        a = parent[a];
    }
    return a;
}

void reset (int *parent, int parentLen)
{
    int i = 0;
    for (; i < parentLen; i++)
    {
            parent[i] = i;
    }
}

void merge (int *parent, int parentLen, int a, int b)
{
    int aRoot = find(parent, parentLen, a);
    int bRoot = find(parent, parentLen, b);
    parent[aRoot] = bRoot;
    while (a != aRoot)
    {
        int tempParent = parent[a];
        parent[a] = bRoot;
        a = tempParent;
    }
}

void generateNextPosArr ()
{
    nextPosArr = (int**) malloc(sizeof(int*) * (strLen + 2));
    int posArr[26];
    int i = 0;
    for (; i < 26; i++)
    {
        posArr[i] = strLen + 2;
    }
    for (i = strLen; i > 0; i--)
    {
        nextPosArr[i] = (int *) malloc (sizeof(int) * 26);
        memcpy(nextPosArr[i], posArr, sizeof(int) * 26);
        posArr[str[i - 1] - 'a'] = i;
    }
    nextPosArr[i] = (int *) malloc (sizeof(int) * 26);
    memcpy(nextPosArr[i], posArr, sizeof(int) * 26);
}

void generatePrevPosArr ()
{
    prevPosArr = (int**) malloc(sizeof(int*) * (strLen + 2));
    int posArr[26];
    int i = 0;
    for (; i < 26; i++)
    {
        posArr[i] = -1;
    }
    for (i = 1; i <= strLen; i++)
    {
        prevPosArr[i] = (int *) malloc (sizeof(int) * 26);
        memcpy(prevPosArr[i], posArr, sizeof(int) * 26);
        posArr[str[i - 1] - 'a'] = i;
    }
    prevPosArr[i] = (int *) malloc (sizeof(int) * 26);
    memcpy(prevPosArr[strLen + 1], posArr, sizeof(int) * 26);
}

int computeMaxPseudoIsomorphicLen (int ind1, int ind2, int blockInd)
{
    if (blockInd == 0)
        return 1;

    while (rankArr[ind1][blockInd - 1] != rankArr[ind2][blockInd - 1])
        blockInd--;

    int prevBlockInd = blockInd - 1;
    int prevBlockLen = 1 << prevBlockInd;
    int blockLen = 1 << blockInd;

    if (ind1 + prevBlockLen >= strLen || ind2 + prevBlockLen >= strLen)
        return prevBlockLen;
    //check that the jumps match
    int charPos11__ = 0;
    int charPos12__ = 0;
    int charPos21__ = 0;
    int charPos22__ = 0;
    int minPos = prevBlockLen;
    int c = 0;
    for (; c < 26; c++)
    {
        charPos11__ = max(-1, prevPosArr[ind1 + prevBlockLen + 1][c] - ind1 - 1);
        charPos12__ = min(prevBlockLen, nextPosArr[ind1 + prevBlockLen][c] - ind1 - prevBlockLen - 1);
        if (charPos11__ != -1 && charPos12__ != prevBlockLen)
        {
            charPos22__ = min(prevBlockLen, nextPosArr[ind2 + prevBlockLen][str[ind2 + charPos11__] - 'a'] - ind2 - prevBlockLen - 1);
            int pos1 = charPos12__;
            int pos2 = charPos22__;
            if (pos1 != pos2)
            {
                int breakPos = min(pos1, pos2);
                minPos = min(breakPos, minPos);
            }
        }
        charPos21__ = max(-1, prevPosArr[ind2 + prevBlockLen + 1][c] - ind2 - 1);
        charPos22__ = min(prevBlockLen, nextPosArr[ind2 + prevBlockLen][c] - ind2 - prevBlockLen - 1);
        if (charPos21__ != -1 && charPos22__ != prevBlockLen)
        {
            charPos12__ =min(prevBlockLen, nextPosArr[ind1 + prevBlockLen][str[ind1 + charPos21__] - 'a'] - ind1 - prevBlockLen - 1);
            int pos2 = charPos22__;
            int pos1 = charPos12__;
            if (pos1 != pos2)
            {
                int breakPos = min(pos1, pos2);
                minPos = min(breakPos, minPos);
            }
        }
    }
   //
    if (rankArr[ind1 + prevBlockLen][prevBlockInd] == rankArr[ind2 + prevBlockLen][prevBlockInd])
        return prevBlockLen + minPos;
    //
    int tempBlockInd = prevBlockInd;
    while (rankArr[ind1 + prevBlockLen][tempBlockInd] != rankArr[ind2 + prevBlockLen][tempBlockInd])
    {
        tempBlockInd--;
    }
    //
    if (minPos < (1 << tempBlockInd))
        return prevBlockLen + minPos;
    //
    int isoLen2 = computeMaxPseudoIsomorphicLen(ind1 + prevBlockLen, ind2 + prevBlockLen, prevBlockInd);
    return prevBlockLen + min(minPos, isoLen2);
}

int comparePseudoIsomorphicLen (const void* ind1_, const void* ind2_)
{
    int ind1 = *((int*) ind1_);
    int ind2 = *((int*) ind2_);
    if (currBlockInd == 0)
        return 0;
    int prevBlockInd = currBlockInd - 1;
    int prevBlockLen = 1 << prevBlockInd;

    if (rankArr[ind1][prevBlockInd] != rankArr[ind2][prevBlockInd])
        return rankArr[ind1][prevBlockInd] - rankArr[ind2][prevBlockInd];

    if (ind1 + prevBlockLen >= strLen)
        return -1;
    else if (ind2 + prevBlockLen >= strLen)
        return 1;

    //check that the jumps match
    int charPos11__ = 0;
    int charPos12__ = 0;
    int charPos21__ = 0;
    int charPos22__ = 0;
    int minPos = prevBlockLen;
    int jumpFrom = -1;
    int result = 0;
    int c = 0;
    for (; c < 26; c++)
    {
        charPos11__ = max(-1, prevPosArr[ind1 + prevBlockLen + 1][c] - ind1 - 1);
        charPos12__ = min(prevBlockLen, nextPosArr[ind1 + prevBlockLen][c] - ind1 - prevBlockLen - 1);
        if (charPos11__ != -1 && charPos12__ != prevBlockLen)
        {
            charPos22__ = min(prevBlockLen, nextPosArr[ind2 + prevBlockLen][str[ind2 + charPos11__] - 'a'] - ind2 - prevBlockLen - 1);
            int pos1 = charPos12__;
            int pos2 = charPos22__;
            if (pos1 != pos2)
            {
                int breakPos = min(pos1, pos2);
                result = breakPos < minPos || (breakPos == minPos && charPos11__ < jumpFrom)
                        ? (pos1 < pos2 ? - 1 : 1) : result;
                jumpFrom = breakPos < minPos ? charPos11__
                        : breakPos == minPos ? min(charPos11__, jumpFrom) : jumpFrom;
                minPos = min(breakPos, minPos);
            }
        }
        charPos21__ = max(-1, prevPosArr[ind2 + prevBlockLen + 1][c] - ind2 - 1);
        charPos22__ = min(prevBlockLen, nextPosArr[ind2 + prevBlockLen][c] - ind2 - prevBlockLen - 1);
        if (charPos21__ != -1 && charPos22__ != prevBlockLen)
        {
            charPos12__ =min(prevBlockLen, nextPosArr[ind1 + prevBlockLen][str[ind1 + charPos21__] - 'a'] - ind1 - prevBlockLen - 1);
            int pos2 = charPos22__;
            int pos1 = charPos12__;
            if (pos1 != pos2)
            {
                int breakPos = min(pos1, pos2);
                result = breakPos < minPos || (breakPos == minPos && charPos21__ < jumpFrom)
                        ? (pos1 < pos2 ? - 1 : 1) : result;
                jumpFrom = breakPos < minPos ? charPos21__
                        : breakPos == minPos ? min(charPos21__, jumpFrom) : jumpFrom;
                minPos = min(breakPos, minPos);
            }
        }
    }
    //
    if (rankArr[ind1 + prevBlockLen][prevBlockInd] == rankArr[ind2 + prevBlockLen][prevBlockInd])
        return result;
    //
    int tempBlockInd = prevBlockInd;
    while (rankArr[ind1 + prevBlockLen][tempBlockInd] != rankArr[ind2 + prevBlockLen][tempBlockInd])
    {
        tempBlockInd--;
    }
    if (minPos < (1 << tempBlockInd))
        return result;
    else if (minPos >= (1 << (tempBlockInd + 1)))
        return rankArr[ind1 + prevBlockLen][prevBlockInd] - rankArr[ind2 + prevBlockLen][prevBlockInd];
    //
    int isoLen2 = computeMaxPseudoIsomorphicLen(ind1 + prevBlockLen, ind2 + prevBlockLen, prevBlockInd);
    int res = minPos <= isoLen2 ? result
            : (rankArr[ind1 + prevBlockLen][prevBlockInd] - rankArr[ind2 + prevBlockLen][prevBlockInd]);
    return res;
}


int comparator (const void* ind1_, const void* ind2_)
{
    int result = comparePseudoIsomorphicLen(ind1_, ind2_);
    if (result == 0)
    {
        merge(parent, strLen, *(int *)(ind1_), *(int *)(ind2_));
    }
    return result;
}

struct Stack
{
    int *values;
    int size;
};
typedef struct Stack Stack;

void init (Stack* stack, int maxSize)
{
    stack->values = malloc(sizeof(int) * maxSize);
    stack->size = 0;
}

void push (Stack* stack, int value)
{
    stack->values[(stack->size)++] = value;
}

int pop (Stack* stack)
{
    int val = stack->values[stack->size - 1];
    (stack->size)--;
    return val;
}

int peek (Stack* stack)
{
    return stack->values[stack->size - 1];
}

int isEmpty (Stack* stack)
{
    return stack->size == 0 ? 1 : 0;
}

void printArr (int *arr, int len)
{
    print("[");
    int i = 0;
    for (; i < len - 1; i++)
    {
        print("%d, ", arr[i]);
    }
    print("]\n");
}
long* countPrefixes_ (int* indices)
{
    long* count = (long *) malloc(sizeof(long) * strLen);
    int isoLen[strLen];
    int suffixInd[strLen];
    suffixInd[indices[0]] = 0;
    int i = 0;
    for (i = 1; i < strLen; i++)
    {
        isoLen[i] = computeMaxPseudoIsomorphicLen(indices[i - 1], indices[i], maxBlockCount - 1);
        suffixInd[indices[i]] = i;
    }
    Stack *stack = (Stack *) malloc(sizeof(Stack));
    init(stack, strLen);
    int* maxIsoArr = malloc(sizeof(int) * strLen);
    int* nextMaxIsoArr = malloc(sizeof(int) * strLen);
    int maxIsoLen = 0;
    //print("2, nono\n");
    for (i = 0; i < strLen; i++)
    {
        maxIsoLen = isoLen[i];
        while (!isEmpty(stack) && indices[peek(stack)] < indices[i])
        {
            //print("____ i = %d\n", i);
            int val = pop(stack);
            //print("____ i = %d k = %d\n", i, k);
            maxIsoLen = min(maxIsoLen, maxIsoArr[val]);
        //print("444444444444\n");
            //pop(stack);
        }
        //print("2. i =%d\n", i);
        push(stack, i);
          //  print("3. i =%d\n", i);
        maxIsoArr[i] = maxIsoLen;
    }
    stack->size = 0;
    //print("3, nono\n");
    for (i = strLen - 1; i >= 0; i--)
    {
        maxIsoLen = i == strLen - 1 ? 0 : isoLen[i + 1];
        while (!isEmpty(stack) && indices[peek(stack)] < indices[i])
        {
            int val = pop(stack);
            maxIsoLen = min(maxIsoLen, nextMaxIsoArr[val]);
            //pop(stack);
        }
        maxIsoLen = isEmpty(stack) ? 0 : min(maxIsoLen, isoLen[peek(stack)]);
        push(stack, i);
        nextMaxIsoArr[i] = maxIsoLen;
        //max(nextMaxIsoArr[i], maxIsoLen);
    }
    //print("1. hoho\n");
    count[strLen - 1] = 1;
    for (i = strLen - 2; i >= 0; i--)
    {
        //if (i % 1000 == 0)
          //  print("i = %d\n", i);
        int ind = suffixInd[i];
        int suffixLen = strLen - i;
        int maxIso = max(nextMaxIsoArr[ind], maxIsoArr[ind]);
        /*if (lastGreaterInd[ind] != -1)
        {
            //print("2. hoho\n");
            maxIso = findMin(tree, lastGreaterInd[ind] + 1, ind);
            //print("21. hoho\n");
        }
        if (nextGreaterInd[ind] != strLen)
        {
            //print("3. hoho\n");
            maxIso = max(maxIso, findMin(tree, ind + 1, nextGreaterInd[ind]));
            //print("31. hoho\n");
        }*/
        count[i] = count[i + 1] + suffixLen - maxIso;
    }
    return count;
}

long* countPrefixes ()
{
    int i = 0;
    //reverse the string
    //print ("SOME %d\n", strLen);
    for (; i < (strLen / 2); i++)
    {
        char tempChar = str[i];
        str[i] = str[strLen - i - 1];
        str[strLen - i - 1] = tempChar;
    }
    //pre processing
    generatePrevPosArr();
    generateNextPosArr();

    //
    maxBlockCount = (int) ceil(log(strLen) / log(2)) + 1;
    rankArr = (int **) malloc (sizeof(int*) * strLen);
    int* indices = malloc(sizeof(int) * strLen);
    for (i = 0; i < strLen; i++)
    {
        indices[i] = i;
        rankArr[i] = (int *) malloc(sizeof(int) * maxBlockCount);
    }

    //
    parent = malloc(sizeof(int) * strLen);
    currBlockInd = 0;

    for (; currBlockInd < maxBlockCount; currBlockInd++)
    {
        qsort(indices, strLen, sizeof(int), comparator);
        //post script
        int counter = 0;
        rankArr[indices[0]][currBlockInd] = counter;
        for (i = 1; i < strLen; i++)
        {

            if (find(parent, strLen, indices[i - 1]) != find(parent, strLen, indices[i]))
                counter++;
            rankArr[indices[i]][currBlockInd] = counter;
        }
        if (currBlockInd < maxBlockCount - 1)
            reset(parent, strLen);
    }
    return countPrefixes_(indices);
}



int main (int argc, char **argv)
{
//        BufferedReader reader = new BufferedReader(new FileReader("D:\\input04.txt"));
//        BufferedReader reader = new BufferedReader(new FileReader("D:\\input31.txt"));
//    BufferedReader reader = new BufferedReader(new FileReader("D:\\input39.txt"));
//        BufferedReader reader = new BufferedReader(new FileReader("D:\\input37.txt"));
//        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    /*FILE *fp;
    //fp = fopen("test", "r");
    fp = fopen("input04.txt", "r");
    */
    str = (char *) malloc(sizeof(char) * 100001);
    /*str = fgets(str, 100001, fp);
    strLen = strlen(str);
    strLen--;
    str[strLen] = '\0';
    fclose(fp);
    //printf("%s---%d\n", str);
    */
    gets(str);
    strLen = strlen(str);
    long* arr = countPrefixes();
    int i = 0;
    int pos = 0;
    int maxResultSize = strLen * 50;
    char *result = malloc(sizeof(char) * maxResultSize);
    for (i = strLen - 1; i > 0; i--)
    {
        pos += snprintf(result + pos, maxResultSize - pos, "%ld\n", arr[i]);
    }
    snprintf(result + pos, maxResultSize - pos, "%ld", arr[i]);
    printf("%s", result);
}

Pytho 2 Pseudo-Isomorphic Substrings HackerRank Solution


Copy Code Copied Use a different Browser

input_str = raw_input().strip()


def preprocess(_str):
    prev_smbls = dict()
    _a = list()
    for i in range(len(_str)):
        if _str[i] in prev_smbls:
            _a.append(i - prev_smbls[_str[i]])
        else:
            _a.append(i + 1)
        prev_smbls[_str[i]] = i
    return _a, prev_smbls


a, prev_symbols = preprocess(input_str)


class Node:
    def __init__(self, **d):
        self.__dict__ = d


class Edge:
    def __init__(self, **d):
        self.__dict__ = d


root = Node(edges=dict(), depth=0, slink=None)
def_edge = Edge(a=root, b=root, u=0, length=0)
curr_edge = (def_edge, 0, 0)
leaves_counter = 0
result = 0


def convert(_c, depth):
    return -1 if _c > depth else _c


def simplify(_curr_edge):
    edge, u, l = _curr_edge
    while l > edge.length:
        c = convert(a[u + edge.length], edge.a.depth + edge.length)
        edge, u, l = edge.b.edges[c], u + edge.length, l - edge.length
    return edge, u, l


def slink(_curr_edge):
    edge, u, length = _curr_edge
    if edge.a == root:
        assert (edge != def_edge)
        return simplify((def_edge, u + 1, length - 1))
    else:
        edge.a.slink = simplify(edge.a.slink)
        tmp_edge, u1, tmp_length = edge.a.slink
        return simplify((tmp_edge, u - tmp_length, length + tmp_length))


for i in range(len(input_str)):
    while True:
        edge, u, length = curr_edge
        c = convert(a[i], edge.a.depth + length)
        if length == edge.length:
            if c in edge.b.edges:
                break
            leaves_counter += 1
            leaf = Node(depth=-1, slink=None, edges=dict())
            edge.b.edges[c] = Edge(a=edge.b, b=leaf, u=i, length=len(input_str) - i)
        else:
            c1 = convert(a[edge.u + length], edge.a.depth + length)
            if c == c1:
                break
            leaves_counter += 1
            leaf = Node(depth=-1, slink=None, edges=dict())
            branch = Node(edges=dict(), depth=edge.a.depth + length, slink=slink(curr_edge))
            branch.edges[c] = Edge(a=branch, b=leaf, u=i, length=len(input_str) - i)
            branch.edges[c1] = Edge(a=branch, b=edge.b, u=edge.u + length, length=edge.length - length)
            edge.b = branch
            edge.length = length
        if edge == def_edge and length == 0:
            curr_edge = None
            break
        if edge.a == root:
            assert (edge != def_edge)
            curr_edge = simplify((def_edge, u + 1, length - 1))
        else:
            edge.a.slink = simplify(edge.a.slink)
            tmp_edge, tmp_u, tmp_length = edge.a.slink
            curr_edge = simplify((tmp_edge, u - tmp_length, length + tmp_length))
    if curr_edge is None:
        curr_edge = def_edge, i + 1, 0
    else:
        edge, u, length = curr_edge
        assert (u + length == i)
        curr_edge = simplify((edge, u, length + 1))
    result += leaves_counter
    print(result)

Leave a comment below

Related posts:

15 Days to learn SQL Hard SQL(Advanced)-SolutionTwo Two – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionTwo Strings Game – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionLetter Islands – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionMorgan and a String – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionAshton and String – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionFind Strings – HackerRank Solution
Tags: Cc++14full solutionGoHackerRank Solutionjavajava 15java 7java 8java8javascriptPseudo-Isomorphic Substringspypy 3Python 2python 3
ShareTweetPin
bhautik bhalala

bhautik bhalala

Related Posts

Updates

Find out how the cast and crew of Classroom of the Elite II prepare for each episode.

by admin
September 8, 2022
0
0

The cast and crew of Classroom of the Elite II discuss their approach to the show and how they prepare...

Read more

Nano Machine Anime Release Date: Plot, Trailer Announcement OUT

September 7, 2022
0
Lookism

Will There Be A Lookism Anime Adaptation from Manga? Release Date And Plot!

September 7, 2022
3

What Happened to Lazar Angelov?

September 5, 2022
3

Tony Beets Net Worth 2022: How Rich Is the Gold Rush Star?

September 5, 2022
1

Robert Kiyosaki Net Worth 2022: How he Made his Money

September 5, 2022
0
Next Post
ESL confirms IEM Rio 2022 CSGO Major

ESL confirms IEM Rio 2022 CSGO Major

15 Days to learn SQL Hard SQL(Advanced)-Solution

Making Candies - HackerRank Solution

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

You may also like

15 Days to learn SQL Hard SQL(Advanced)-SolutionTwo Two – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionTwo Strings Game – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionLetter Islands – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionMorgan and a String – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionAshton and String – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionFind Strings – HackerRank Solution

Categories

  • Algorithms
  • Anime
  • Biography
  • Business
  • Code Solutions
  • Cosmos
  • Countdowns
  • Culture
  • Economy
  • Education
  • Entertainment
  • Finance
  • Games
  • Hackerrank
  • Health
  • How to
  • Investment
  • LeetCode
  • Lifestyle
  • LINUX SHELL
  • Manga
  • News
  • Opinion
  • Politics
  • Sports
  • SQL
  • Tech
  • Travel
  • Uncategorized
  • Updates
  • World
  • DMCA
  • Home
  • My account
  • Privacy Policy
  • Top Posts

Recent Blogs

Leetcode All Problems Solutions

Exclusive Time of Functions – LeetCode Solution

October 5, 2022
Leetcode All Problems Solutions

Smallest Range Covering Elements from K Lists – LeetCode Solution

October 5, 2022
Leetcode All Problems Solutions
Code Solutions

Combination Sum – LeetCode Solution

September 3, 2022
71
Shark Tank
Business

Grill Charms Shark Tank Update Everything You need to know.

September 5, 2022
1
Mercenary Enrollment
Anime

Mercenary Enrollment Chapter 100 Raw Scan English Spoilers

August 30, 2022
9
Eleceed Chapter 210 Raw Scan Early Spoilers
Anime

Eleceed Chapter 210 Raw Scan Early Spoilers: Jiwoo’s Electro Attack

September 1, 2022
104

© 2022 ZeroPlusFour - Latest News & Blog.

No Result
View All Result
  • Home
  • Category
    • Business
    • Culture
    • Economy
    • Lifestyle
    • Health
    • Travel
    • Opinion
    • Politics
    • Tech
  • Landing Page
  • Support Forum
  • Contact Us

© 2022 ZeroPlusFour - Latest News & Blog.

Welcome Back!

Login to your account below

Forgotten Password?

Retrieve your password

Please enter your username or email address to reset your password.

Log In
We use cookies on our website to give you the most relevant experience by remembering your preferences and repeat visits. By clicking “Accept All”, you consent to the use of ALL the cookies. However, you may visit "Cookie Settings" to provide a controlled consent.
Cookie SettingsAccept All
Manage consent

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. These cookies ensure basic functionalities and security features of the website, anonymously.
CookieDurationDescription
cookielawinfo-checkbox-analytics11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Analytics".
cookielawinfo-checkbox-functional11 monthsThe cookie is set by GDPR cookie consent to record the user consent for the cookies in the category "Functional".
cookielawinfo-checkbox-necessary11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookies is used to store the user consent for the cookies in the category "Necessary".
cookielawinfo-checkbox-others11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Other.
cookielawinfo-checkbox-performance11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Performance".
viewed_cookie_policy11 monthsThe cookie is set by the GDPR Cookie Consent plugin and is used to store whether or not user has consented to the use of cookies. It does not store any personal data.
Functional
Functional cookies help to perform certain functionalities like sharing the content of the website on social media platforms, collect feedbacks, and other third-party features.
Performance
Performance cookies are used to understand and analyze the key performance indexes of the website which helps in delivering a better user experience for the visitors.
Analytics
Analytical cookies are used to understand how visitors interact with the website. These cookies help provide information on metrics the number of visitors, bounce rate, traffic source, etc.
Advertisement
Advertisement cookies are used to provide visitors with relevant ads and marketing campaigns. These cookies track visitors across websites and collect information to provide customized ads.
Others
Other uncategorized cookies are those that are being analyzed and have not been classified into a category as yet.
SAVE & ACCEPT
Are you sure want to unlock this post?
Unlock left : 0
Are you sure want to cancel subscription?