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
#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
// 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
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
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
#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
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)
