HackerRank Pseudo-Isomorphic Substrings Yashwant Parihar, May 2, 2023May 2, 2023 In this post, we will solve HackerRank Pseudo-Isomorphic Substrings Problem Solution. Two strings A and B, consisting of small English alphabet letters are called pseudo-isomorphic if Their lengths are equal For every pair (i,j), where 1 <= i < j <= |A|, B[i] = B[j], iff A[i] = A[j] For every pair (i,j), where 1 <= i < j <= |A|, B[i] != B[j] iff A[i] != A[j] Naturally, we use 1-indexation in these definitions and |A| denotes the length of the string A. You are given a string S, consisting of no more than 105 lowercase alphabetical characters. For every prefix of S denoted by S’, you are expected to find the size of the largest possible set of strings , such that all elements of the set are substrings of S’ and no two strings inside the set are pseudo-isomorphic to each other. if S = abcdethen, 1st prefix of S is ‘a’then, 2nd prefix of S is ‘ab’then, 3rd prefix of S is ‘abc’then, 4th prefix of S is ‘abcd’ and so on.. Input Format The first and only line of input will consist of a single string S. The length of S will not exceed 10^5. Constraints S contains only lower-case english alphabets (‘a’ – ‘z’). Output Format Output N lines. On the ith line, output the size of the largest possible set for the first i alphabetical characters of S such that no two strings in the set are pseudo-isomorphic to each other. Sample Input abbabab Sample Output 1 2 4 6 9 12 15 Explanation The first character is ‘a’, the set is {a} hence 1.The first 2 characters are ‘ab’, the set is {a, b, ab} but ‘a’ is pseudo-isomorphic to ‘b’. So, we can remove either ‘a’ or ‘b’ from the set. We get {a,ab} or {b,ab}, hence 2.Similarly, the first 3 characters are ‘abb’, the set is {a, ab, abb, b, bb} and as ‘a’ is pseudo-isomorphic to ‘b’, we have to remove either ‘a’ or ‘b’ from the set. We get {a,ab, abb, bb}, hence 4. and so on… HackerRank Pseudo-Isomorphic Substrings Problem Solution Pseudo-Isomorphic Substrings C 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); } Pseudo-Isomorphic Substrings C++ Solution #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; } Pseudo-Isomorphic Substrings C Sharp Solution using System; using System.Collections.Generic; using System.Diagnostics; using System.IO; using System.Linq; using System.Text; namespace HackerRanking { internal class SolutionPseudoIsomorphicSubstrings { private static unsafe void Main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */ TextReader reader = null; try { reader = new StringReader(@"abbabab"); reader = File.OpenText(@"c:\temp\input37-PseudoIsomorphicSubstrings.txt"); } catch { reader = Console.In; } if (reader == TextReader.Null) return; var sb = new StringBuilder(); var s = reader.ReadLine(); //solve(s, sb); var solver = new PseudoIsomorphic(s); solver.solve(sb); //File.WriteAllText(@"c:\temp\output.txt", sb.ToString()); Console.WriteLine(sb.ToString()); } public static void solve(string s, StringBuilder sb) { //s = "qwesaaawaa"; int n = s.Length; int[] lcp; int[] sa; isosubstring.BuildSuffixArray(s, out sa, out lcp); #if TEST var a = new int[s.Length + 1]; for (var i = 0; i < s.Length; i++) a[i] = s[i]; var sa1 = SuffixArray.buildSuffixArray(a); var lcp1 = SuffixArray.getLCP(sa, a); Debug.Assert(sa1.SequenceEqual(sa)); Debug.Assert(lcp1.SequenceEqual(lcp)); var distinct = (long)isosubs[1].Length; for (int i = 2; i < isosubs.Length; i++) { distinct += isosubs[i].Length - lcp[i-1]; } #endif var minTree = new MinSegmentTree(n + 1); var where = new int[sa.Length]; for (var i = 0; i < sa.Length; i++) where[sa[i]] = i; var stable = new SparseTableMin(lcp); var fSum = new FenwickMultiSum(n); var results = new long[n]; for (var i = n - 1; i >= 0; i--) { var suffix = where[i]; var curLen = 0; while (true) { var left = -1; var right = suffix; while (left < right - 1) { var mid = (left + right) >> 1; if (stable.getMin(mid, suffix) <= curLen) left = mid; else right = mid; } var first = right; left = suffix - 1; right = n + 1; while (left < right - 1) { var mid = (left + right) >> 1; if (stable.getMin(suffix, mid + 1) <= curLen) right = mid; else left = mid; } var last = right; var j = minTree.getMin(first, last + 1); if (j == int.MaxValue) break; var nextSuffix = where[j]; var curLCP = nextSuffix < suffix ? stable.getMin(nextSuffix, suffix) : stable.getMin(suffix, nextSuffix); fSum.add(j + curLen, j + curLCP, -1); curLen = curLCP; } minTree.set(suffix, i); fSum.add(i, n, 1); } for (int i = 0; i < n; i++) results[i] = fSum.getSum(0, i + 1); foreach (var e in results) sb.AppendLine(e.ToString()); Console.WriteLine(max); } static int max = 0; private static int[] prevOccurence; public static int[] GetPrevOccurence(string s) { int[] tracking = Enumerable.Range(1, NumChars) .Select(i => -1) .ToArray(); var res = new int[s.Length]; res[s.Length - 1] = -1; for (int i = 0; i < s.Length; i++) { res[i] = tracking[s[i] - 'a']; tracking[s[i] - 'a'] = i; } return res; } private const int NumChars = 26; public const int Mod = 1000000007; public static ulong[] powers = null;//computePowers(100000); public static ulong[] computePowers(int n) { var res = new ulong[n+1]; var pow = 1UL; for (int i = 0; i < n; i++) { res[i] = pow; pow = (pow * NumChars) % Mod; } return res; } public static unsafe int GetHash(char* a, int pos, int len, out long[] sig_buckets) { //long siga = 0; sig_buckets = new long[NumChars]; for (int i = 0; i < len; ++i) { sig_buckets[a[pos + i] - 'a'] += ((long)powers[i] * (a[pos + i] - 'a')); sig_buckets[a[pos + i] - 'a'] %= Mod; //siga += ((long)powers[i] * (a[p + i] - 'a')) % Mod; //siga = siga%Mod; } return (int)(sig_buckets.Sum()%Mod); } public static unsafe bool AreSimilar(char* s, int pos1, int pos2, int len) { //f("abacaba") =[1, 2, 2, 4, 2, 4, 2] // = -1,-1, 0,-1, 2, 1, 4 // = 1, 2, 3, 2, 4, 2 //f("aba") = [1,2,2] //f("bac") = [1,2,3] //f("aca") = [1,2,2] //f("cab") = [1,2,3] for (int k = 0; k < len; k++) { var idx1 = k - ((prevOccurence[k + pos1] < pos1) ? -1 : prevOccurence[k + pos1] - pos1); var idx2 = k - ((prevOccurence[k + pos2] < pos2) ? -1 : prevOccurence[k + pos2] - pos2); if (idx2 != idx1) return false; } return true; } public unsafe class isosubstring : IComparable<isosubstring> { public readonly int pos; public readonly int Length; public readonly char* ps; public isosubstring(char* s, int pos, int length) { this.pos = pos; this.Length = length; ps = s; } public static void BuildSuffixArray(string s, out int[] sa, out int[] lcp) { prevOccurence = GetPrevOccurence(s); fixed (char* ps = s) { char* ps1 = ps; var isosa = Enumerable .Range(0, s.Length) .Select(i => new isosubstring(ps1, i, s.Length - i)) .ToList(); isosa.Sort(); isosa.Insert(0, new isosubstring(ps, s.Length, 1)); sa = isosa.Select(t => t.pos).ToArray(); /* lcp = getLCP(sa); lcp[0] = 0; */ lcp = new int[s.Length+1]; for (int i = 2; i < isosa.Count; i++) lcp[i-1] = isosa[i].computeLcp(isosa[i - 1]); //Debug.Assert(lcp1.SequenceEqual(lcp)); } } //static void sort(List<isosubstring> ) static int[] getLCP(int[] sa) { var k = 0; var n = sa.Length; var rev = new int[n]; for (var i = 0; i < n; i++) rev[sa[i]] = i; var lcp = new int[n]; for (var i = 0; i < n; i++) { k = Math.Max(k - 1, 0); var j = rev[i] + 1; if (j >= n) continue; j = sa[j]; while (i + k < n && j + k < n && convert(i , k) == convert(j, k)) ++k; lcp[rev[i]] = k; } return lcp; } static int convert(int p, int k) { var res = k - ((k+p>=prevOccurence.Length || prevOccurence[k + p] < p) ? -1 : prevOccurence[k + p] - p); max = Math.Max(max, res); return res; } public int computeLcp(isosubstring other) { var pos1 = pos; var pos2 = other.pos; var len = Math.Min(Length, other.Length); int k = 0; for (; k < len; k++) { if (k + pos1 >= prevOccurence.Length || k + pos2 >= prevOccurence.Length) break; var idx1 = convert(pos1, k);//k - ((prevOccurence[k + pos1] < pos1) ? -1 : prevOccurence[k + pos1] - pos1);//ps[k + pos1]; var idx2 = convert(pos2, k);//k - ((prevOccurence[k + pos2] < pos2) ? -1 : prevOccurence[k + pos2] - pos2);//ps[k + pos2];// if (idx2 != idx1) break; } return k; } public int CompareTo(isosubstring other) { var pos1 = pos; var pos2 = other.pos; var len = Math.Min(Length, other.Length); for (int k = 0; k < len; k++) { var idx1 = convert(pos1, k);//k - ((prevOccurence[k + pos1] < pos1) ? -1 : prevOccurence[k + pos1] - pos1));//ps[k + pos1]; var idx2 = convert(pos2, k);//k - ((prevOccurence[k + pos2] < pos2) ? -1 : prevOccurence[k + pos2] - pos2));//ps[k + pos2];// if (idx2 != idx1) return idx1.CompareTo(idx2); } return Length.CompareTo(other.Length); } public char this[int i] { get { return ps[pos + i]; } } public override unsafe int GetHashCode() { var plastx = new char[NumChars]; var it = (char)0; long hash1 = 5381; for (var i = pos; i < pos + Math.Min(Length, 12); i++) { var idx = ps[i] - 'a'; if (plastx[idx] == 0) plastx[idx] = ++it; var e = plastx[idx]; hash1 = (hash1 * e + 33) % Mod; } return (int)(hash1 & 0xffffff); } public override string ToString() { return string.Format("{0}-{1}", pos, Length); } } } public class PseudoIsomorphic { private class Node { public Dictionary<int,Edge> edges = new Dictionary<int, Edge>(); public int depth = 0; public Link slink = null; }; private class Edge { public Node left; public Node right; public int upper; public int lower; }; private class Link { public Edge edge; public int u; public int l; } private readonly List<int> prevIndex; private readonly Node root; private readonly Edge edge0; int leaves = 0; long ans = 0; readonly Dictionary<int, int> prevs = new Dictionary<int,int>(); private string s; public PseudoIsomorphic(string s) { this.s = s; prevIndex = new List<int>(); for (int j = 0; j < s.Length; j++) { if(prevs.ContainsKey(s[j])) prevIndex.Add(j - prevs[s[j]]); else prevIndex.Add(j+1); prevs[s[j]] = j; } root = new Node() {edges = new Dictionary<int, Edge>(), depth = 0, slink = null}; edge0 = new Edge() {left =root, right = root, upper = 0, lower = 0}; var max = prevIndex.Max(); } int conv(int c, int depth) { return c > depth ? -1 : c; } Link simplify(Link link) { return simplify(link.edge, link.u, link.l); } Link simplify(Edge edge, int u, int l) { while (l > edge.lower) { var c = conv(prevIndex[u + edge.lower], edge.left.depth + edge.lower); u = u + edge.lower; l = l - edge.lower; edge = edge.right.edges[c]; } return new Link(){edge= edge, u = u, l = l}; } Link slink(Link link) { var edge = link.edge; if (edge.left == root) return simplify(edge0, link.u + 1, link.l - 1); else { edge.left.slink = simplify(edge.left.slink); var l1 = edge.left.slink.l; return simplify(edge.left.slink.edge, link.u - l1, link.l + l1); } } public long solve(StringBuilder sb) { var current = new Link() {edge = edge0, u = 0, l = 0 }; for (var i = 0; i < s.Length; i++) { while (true) { var edge = current.edge; var u = current.u; var l = current.l; var c = conv(prevIndex[i], edge.left.depth + l); if (l == edge.lower) { //this 'in' if (edge.right.edges.ContainsKey(c)) break; leaves += 1; var leaf = new Node() {depth = -1, slink = null, edges = new Dictionary<int, Edge>()}; edge.right.edges[c] = new Edge() {left = edge.right, right = leaf, upper = i, lower = s.Length - i}; } else { var c1 = conv(prevIndex[edge.upper + l], edge.left.depth + l); if (c == c1) break; leaves += 1; var leaf = new Node() {depth = -1, slink = null, edges = new Dictionary<int, Edge>()}; var branch = new Node() {edges = new Dictionary<int, Edge>(), depth = edge.left.depth + l, slink = slink(current)}; branch.edges[c] = new Edge() {left = branch, right = leaf, upper = i, lower = s.Length - i}; branch.edges[c1] = new Edge() {left = branch, right = edge.right, upper = edge.upper + l, lower = edge.lower - l}; edge.right = branch; edge.lower = l; } if (edge == edge0 && l == 0) { current = null; break; } if (edge.left == root) current = simplify(edge0, u + 1, l - 1); else { edge.left.slink = simplify(edge.left.slink); var l1 = edge.left.slink.l; current = simplify(edge.left.slink.edge, u - l1, l + l1); } } current = current == null ? new Link() {edge = edge0, u = i + 1, l = 0} : simplify(current.edge, current.u, current.l + 1); ans += (long)leaves; sb.AppendLine(ans.ToString()); } return ans; } } public class SparseTableMin { private readonly int[][] min; private readonly int[] h; public SparseTableMin(int[] a) { h = new int[a.Length + 1]; h[1] = 0; for (var i = 2; i < h.Length; i++) h[i] = h[i >> 1] + 1; min = new int[h[h.Length - 1] + 1][]; for (var i = 0; i < min.Length; i++) min[i] = new int[a.Length]; for (var i = 0; i < a.Length; i++) min[0][i] = a[i]; for (var i = 1; i < min.Length; i++) { var prev = min[i - 1]; var mini = min[i]; for (var v = 0; v < a.Length; v++) { if (v + (1 << (i - 1)) < a.Length) mini[v] = Math.Min(prev[v], prev[v + (1 << (i - 1))]); else mini[v] = prev[v]; } } } public int getMin(int left, int right) { if (right <= left) return int.MaxValue; var k = h[right - left]; var mink = min[k]; var res = Math.Min(mink[left], mink[right - (1 << k)]); return res; } } public class FenwickLong { private long[] a; public FenwickLong(int n) { a = new long[n]; } public void add(int x, long y) { for (var i = x; i < a.Length; i |= i + 1) a[i] += y; } public long getSum(int x) { if (x >= a.Length) x = a.Length - 1; long ret = 0; for (var i = x; i >= 0; i = (i & (i + 1)) - 1) ret += a[i]; return ret; } } public class FenwickMultiSum { private FenwickLong fX; private FenwickLong f; public FenwickMultiSum(int n) { fX = new FenwickLong(n); f = new FenwickLong(n); } private void add(int x, long d) { fX.add(x, d); f.add(x, d * (1 - x)); } public void add(int left, int right, long d) { add(left, d); add(right, -d); } public long getSum(int x) { //2, 3, 1, 4, 6, 0, -1, 12 //2, 0,-1,-8, //(fx() *idx) /* var tmp = fX.getSum(idx); var tmp1 = f.getSum(idx); var tmp2 = f.getSum(idx) + fX.getSum(idx)*idx; */ return f.getSum(x) + fX.getSum(x) * x; } public long getSum(int left, int right) { return getSum(right - 1) - getSum(left - 1); } } public class MinSegmentTree { private int[] min; private int[] minId; private int n; public static int highestOneBit(int i) { i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); return i - (i >> 1); } public MinSegmentTree(int n) { this.n = highestOneBit(n) << 1; min = new int[this.n * 2]; minId = new int[this.n * 2]; for (var i = 0; i < n; i++) minId[i + this.n] = i; for (var i = 0; i < n; i++) set(i, int.MaxValue); } public void set(int idx, int val) { idx += n; min[idx] = val; while (idx > 1) { idx >>= 1; var left = min[idx << 1]; var right = min[(idx << 1) | 1]; if (left <= right) { min[idx] = left; minId[idx] = minId[idx << 1]; } else { min[idx] = right; minId[idx] = minId[(idx << 1) | 1]; } } } public int getMin(int left, int right) { --right; left += n; right += n; var ret = int.MaxValue; while (left <= right) { if ((left & 1) == 1) { ret = Math.Min(ret, min[left]); left++; } if ((right & 1) == 0) { ret = Math.Min(ret, min[right]); right--; } left >>= 1; right >>= 1; } return ret; } } } Pseudo-Isomorphic Substrings Java 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; } } Pseudo-Isomorphic Substrings Python 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 C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython