HackerRank Pseudo-Isomorphic Substrings problem solution YASH PAL, 31 July 202423 January 2026 In this HackerRank Pseudo-Isomorphic Substrings problem solution, two strings A and B, consisting of small English alphabet letters are called pseudo-isomorphic ifTheir lengths are equalFor 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 FormatThe first and only line of input will consist of a single string S. The length of S will not exceed 10^5.HackerRank Pseudo-Isomorphic Substrings problem solution in Python.#!/bin/python3 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) Pseudo-Isomorphic Substrings problem solution in Java.import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class PseudoIsomorphicSubstrings { public static class ST { public static class Node { private final int valuesFromRootCount; private final Map<Integer, Edge> edges; private Node slink; public Node(final int valuesFromRootCount) { this.valuesFromRootCount = valuesFromRootCount; this.edges = new HashMap<>(); } public int getValuesFromRootCount() { return this.valuesFromRootCount; } public void setSlink(final Node slink) { this.slink = slink; } public Map<Integer, Edge> getEdges() { return this.edges; } public Node getSlink() { return this.slink; } } public static class Edge { private final int suffixStartIndex; private final int from; private final int to; private final Node next; public Edge(final int suffixStartIndex, final int from, final int to, final Node next) { this.suffixStartIndex = suffixStartIndex; this.from = from; this.to = to; this.next = next; } public int getSuffixStartIndex() { return this.suffixStartIndex; } public int getFrom() { return this.from; } public int getTo() { return this.to; } public Node getNext() { return this.next; } public int getLength() { return this.to - this.from; } } public static class ActivePoint { private final Node activeNode; private final Integer activeEdgeFirstValue; private final int activeLength; public ActivePoint(final Node activeNode, final Integer activeEdgeFirstValue, final int activeLength) { this.activeNode = activeNode; this.activeEdgeFirstValue = activeEdgeFirstValue; this.activeLength = activeLength; } private Edge getActiveEdge() { return this.activeNode.getEdges().get(this.activeEdgeFirstValue); } private int getActiveValue(final int[] values) { final int valueOnEdgeIndex = getActiveEdge().getFrom() + this.activeLength; return getSuffixValue(getActiveEdge().getSuffixStartIndex(), values, valueOnEdgeIndex); } public int getSuffixValue(final int suffixStartIndex, final int[] values, final int valueIndex) { return suffixStartIndex <= valueIndex - values[valueIndex] ? values[valueIndex] : 0; } public boolean pointsToActiveNode() { return this.activeLength == 0; } public boolean activeNodeIs(final Node node) { return this.activeNode == node; } public boolean activeNodeHasEdgeStartingWith(final int value) { return this.activeNode.getEdges().containsKey(value); } public boolean activeNodeHasSlink() { return this.activeNode.getSlink() != null; } public boolean pointsToOnActiveEdge(final int[] values, final int value) { return getActiveValue(values) == value; } public boolean pointsToTheEndOfActiveEdge() { return this.getActiveEdge().getLength() == this.activeLength; } public boolean pointsAfterTheEndOfActiveEdge() { return this.getActiveEdge().getLength() < this.activeLength; } public ActivePoint moveToEdgeStartingWithAndByOne(final int value) { return new ActivePoint(this.activeNode, value, 1); } public ActivePoint moveToNextNodeOfActiveEdge() { return new ActivePoint(this.getActiveEdge().getNext(), null, 0); } public ActivePoint moveToSlink(final int[] values, final int suffixStartIndex, final int index) { final int slinkIndex = suffixStartIndex + this.activeNode.getSlink().getValuesFromRootCount(); final int slinkValue = getSuffixValue(suffixStartIndex, values, slinkIndex); final int slinkActiveLength = index - slinkIndex; return new ActivePoint(this.activeNode.getSlink(), slinkValue, slinkActiveLength); } public ActivePoint moveTo(final Node node) { return new ActivePoint(node, null, 0); } public ActivePoint moveTo(final Node node, final int activeLength) { return new ActivePoint(node, 0, activeLength); } public ActivePoint moveByOneValue() { return new ActivePoint(this.activeNode, this.activeEdgeFirstValue, this.activeLength + 1); } public ActivePoint moveToNextNodeOfActiveEdge(final int[] values, final int suffixStartIndex) { final int valueAtTheEndOfEdgeIndex = suffixStartIndex + this.activeNode.getValuesFromRootCount() + this.getActiveEdge() .getLength(); final int valueAtTheEndOfEdge = getSuffixValue(suffixStartIndex, values, valueAtTheEndOfEdgeIndex); return new ActivePoint(this.getActiveEdge().getNext(), valueAtTheEndOfEdge, this.activeLength - this.getActiveEdge().getLength()); } public void addEdgeToActiveNode(final int value, final Edge edge) { this.activeNode.getEdges().put(value, edge); } public Node splitActiveEdge(final int[] values, final int suffixStartIndex, final int index, final int value) { final Node newNode = new Node(this.activeNode.getValuesFromRootCount() + this.activeLength); final Edge activeEdgeToSplit = this.getActiveEdge(); final Edge splittedEdge = new Edge(activeEdgeToSplit.getSuffixStartIndex(), activeEdgeToSplit.getFrom(), activeEdgeToSplit.getFrom() + this.activeLength, newNode); newNode.getEdges().put(getActiveValue(values), new Edge(activeEdgeToSplit.getSuffixStartIndex(), activeEdgeToSplit.getFrom() + this.activeLength, activeEdgeToSplit.getTo(), activeEdgeToSplit.getNext())); newNode.getEdges().put(value, new Edge(suffixStartIndex, index, values.length, null)); this.activeNode.getEdges().put(this.activeEdgeFirstValue, splittedEdge); return newNode; } public Node setSlinkTo(final Node previouslyAddedNodeOrAddedEdgeNode, final Node node) { if(previouslyAddedNodeOrAddedEdgeNode != null) { previouslyAddedNodeOrAddedEdgeNode.setSlink(node); } return node; } public Node setSlinkToActiveNode(final Node previouslyAddedNodeOrAddedEdgeNode) { return setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, this.activeNode); } } private final int[] values; private final Node root; private ActivePoint activePoint; private int remainder; private long totalLeavesCount; private long leavesSum; public ST(final int[] values) { this.values = values; this.root = new Node(0); this.activePoint = new ActivePoint(this.root, null, 0); this.remainder = 0; this.totalLeavesCount = 0; this.leavesSum = 0; build(); } private void build() { for(int i = 0; i < this.values.length; i++) { add(i); } } private void add(final int index) { this.remainder++; boolean valueFoundInTheTree = false; Node previouslyAddedNodeOrAddedEdgeNode = null; while(!valueFoundInTheTree && this.remainder > 0) { final int suffixStartIndex = index - this.remainder + 1; final int valueToCheckExistanceInTree = this.activePoint.getSuffixValue(suffixStartIndex, this.values, index); if(this.activePoint.pointsToActiveNode()) { if(this.activePoint.activeNodeHasEdgeStartingWith(valueToCheckExistanceInTree)) { activeNodeHasEdgeStartingWithValue(valueToCheckExistanceInTree, previouslyAddedNodeOrAddedEdgeNode); valueFoundInTheTree = true; } else { if(this.activePoint.activeNodeIs(this.root)) { rootNodeHasNotEdgeStartingWithValue(suffixStartIndex, index, valueToCheckExistanceInTree); } else { previouslyAddedNodeOrAddedEdgeNode = internalNodeHasNotEdgeStartingWithValue( suffixStartIndex, index, valueToCheckExistanceInTree, previouslyAddedNodeOrAddedEdgeNode); } } } else { if(this.activePoint.pointsToOnActiveEdge(this.values, valueToCheckExistanceInTree)) { activeEdgeHasValue(); valueFoundInTheTree = true; } else { if(this.activePoint.activeNodeIs(this.root)) { previouslyAddedNodeOrAddedEdgeNode = edgeFromRootNodeHasNotValue(suffixStartIndex, index, valueToCheckExistanceInTree, previouslyAddedNodeOrAddedEdgeNode); } else { previouslyAddedNodeOrAddedEdgeNode = edgeFromInternalNodeHasNotValue(suffixStartIndex, index, valueToCheckExistanceInTree, previouslyAddedNodeOrAddedEdgeNode); } } } } this.leavesSum += this.totalLeavesCount; System.out.println(this.leavesSum); } private void activeNodeHasEdgeStartingWithValue(final int value, final Node previouslyAddedNodeOrAddedEdgeNode) { this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode); this.activePoint = this.activePoint.moveToEdgeStartingWithAndByOne(value); if(this.activePoint.pointsToTheEndOfActiveEdge()) { this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(); } } private void rootNodeHasNotEdgeStartingWithValue(final int suffixStartIndex, final int index, final int value) { this.activePoint.addEdgeToActiveNode(value, new Edge(suffixStartIndex, index, this.values.length, null)); this.totalLeavesCount++; this.activePoint = this.activePoint.moveTo(this.root); this.remainder--; assert this.remainder == 0; } private Node internalNodeHasNotEdgeStartingWithValue(final int suffixStartIndex, final int index, final int value, Node previouslyAddedNodeOrAddedEdgeNode) { this.activePoint.addEdgeToActiveNode(value, new Edge(suffixStartIndex, index, this.values.length, null)); this.totalLeavesCount++; previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkToActiveNode( previouslyAddedNodeOrAddedEdgeNode); if(this.activePoint.activeNodeHasSlink()) { this.activePoint = this.activePoint.moveToSlink(this.values, suffixStartIndex + 1, index); } else { this.activePoint = this.activePoint.moveTo(this.root, this.remainder - 2); } this.activePoint = walkDown(suffixStartIndex + 1); this.remainder--; return previouslyAddedNodeOrAddedEdgeNode; } private void activeEdgeHasValue() { this.activePoint = this.activePoint.moveByOneValue(); if(this.activePoint.pointsToTheEndOfActiveEdge()) { this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(); } } private Node edgeFromRootNodeHasNotValue(final int suffixStartIndex, final int index, final int value, Node previouslyAddedNodeOrAddedEdgeNode) { final Node newNode = this.activePoint.splitActiveEdge(this.values, suffixStartIndex, index, value); this.totalLeavesCount++; previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode); this.activePoint = this.activePoint.moveTo(this.root, this.remainder - 2); this.activePoint = walkDown(suffixStartIndex + 1); this.remainder--; return previouslyAddedNodeOrAddedEdgeNode; } private Node edgeFromInternalNodeHasNotValue(final int suffixStartIndex, final int index, final int value, Node previouslyAddedNodeOrAddedEdgeNode) { final Node newNode = this.activePoint.splitActiveEdge(this.values, suffixStartIndex, index, value); this.totalLeavesCount++; previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode); if(this.activePoint.activeNodeHasSlink()) { this.activePoint = this.activePoint.moveToSlink(this.values, suffixStartIndex + 1, index); } else { this.activePoint = this.activePoint.moveTo(this.root, this.remainder - 2); } this.activePoint = walkDown(suffixStartIndex + 1); this.remainder--; return previouslyAddedNodeOrAddedEdgeNode; } private ActivePoint walkDown(final int suffixStartIndex) { while(!this.activePoint.pointsToActiveNode() && (this.activePoint.pointsToTheEndOfActiveEdge() || this.activePoint.pointsAfterTheEndOfActiveEdge())) { if(this.activePoint.pointsAfterTheEndOfActiveEdge()) { this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(this.values, suffixStartIndex); } else { this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(); } } return this.activePoint; } } public static void main(final String[] args) { final Scanner in = new Scanner(System.in); final String line = in.next(); final char[] charsLine = line.toCharArray(); final int[] indexesMinusprevOccurenceIndexes = new int[line.length()]; final Map<Character, Integer> prev = new HashMap<>(); for(int i = 0; i < line.length(); i++) { if(prev.containsKey(charsLine[i])) { indexesMinusprevOccurenceIndexes[i] = i - prev.get(charsLine[i]); } prev.put(charsLine[i], i); } new ST(indexesMinusprevOccurenceIndexes); } } Problem solution in C++.#include <algorithm>#include <iostream>#include <sstream>#include <string>#include <vector>#include <queue>#include <set>#include <map>#include <cstdio>#include <cstdlib>#include <cctype>#include <cmath>#include <cstring>#include <ctime>#include <cassert>#include <limits>using namespace std;typedef long long LL;#define FOR(k,a,b) for(int k(a); k < (b); ++k)#define FORD(k,a,b) for(int k(a); k >= (b); --k)#define REP(k,a) for(int k=0; k < (a); ++k)#define ABS(a) ((a)>0?(a):-(a)) typedef vector<int> VI;typedef vector<vector<int> > VVI;typedef vector<vector<bool> > VVB; LL powmod(LL a, LL b,LL p){ LL tmp=a; LL res=1; while(b) { if(b&1) { res*=tmp; res%=p; } tmp*=tmp; tmp%=p; b>>=1; } return res;} int main(){#ifdef HOME freopen ("in.txt","r",stdin); freopen ("out.txt","wb",stdout);#endif char cc[100009]; scanf("%s",cc); int N=strlen(cc); int tmp,ctr; vector<vector<int> > perm(26,vector<int> (N)); vector<int> llast(26); map<int,int> ml; map<int,int>::iterator mit; REP(i,26) { llast[i]=1e6+i; ml[llast[i]]=i; } for(int i=N-1;i>-1;--i) { tmp=cc[i]-'a'; ctr=1; ml.erase(llast[tmp]); llast[tmp]=i; ml[i]=tmp; for(mit=ml.begin();mit!=ml.end();++mit) { perm[mit->second][i]=ctr; ++ctr; } } vector<int> v(N,1e6); LL mod1=1e9+7, factor1=37; vector<LL> factors1(1e5+2); factors1[0]=1; LL inversefactor1=powmod(factor1,mod1-2,mod1); FOR(i,1,factors1.size()) factors1[i]=(factors1[i-1]*factor1)%mod1; map<pair<int,LL>,int> hash; hash[make_pair(0,0)]=0; hash[make_pair(1,1)]=0; v[0]=1; int currlen=1, actsimilar=0; vector<LL> w1(26); w1[cc[1]-'a']++; FOR(st,1,N) { //calculate actual hash LL currhash=0; REP(i,26) { currhash+=w1[i]*perm[i][st]; currhash%=mod1; } //find the first isomorph substring to the current while(hash.count(make_pair(currlen,currhash))) { actsimilar=hash[make_pair(currlen,currhash)]; for(++currlen;st+currlen<=N;++currlen) { w1[cc[st+currlen-1]-'a']+=factors1[currlen-1]; if(w1[cc[st+currlen-1]-'a']>=mod1) w1[cc[st+currlen-1]-'a']-=mod1; currhash+=factors1[currlen-1]*perm[cc[st+currlen-1]-'a'][st]; currhash%=mod1; if(perm[cc[actsimilar+currlen-1]-'a'][actsimilar]!=perm[cc[st+currlen-1]-'a'][st]) { break; } } } if(currlen+st>N) break; assert(!hash.count(make_pair(currlen,currhash))); hash[make_pair(currlen,currhash)]=st;//insert current hash //insert other hash direction currhash+=(mod1-factors1[currlen-1])*perm[cc[st+currlen-1]-'a'][st]; currhash%=mod1; currhash+=(factors1[currlen-1])*perm[cc[actsimilar+currlen-1]-'a'][actsimilar]; currhash%=mod1; if(!hash.count(make_pair(currlen,currhash))) { hash[make_pair(currlen,currhash)]=actsimilar; } v[st]=currlen; //delete first character w1[cc[st]-'a']--; if(w1[cc[st]-'a']<0) w1[cc[st]-'a']+=mod1; --currlen; if(currlen>1) { w1[cc[st+currlen]-'a']-=factors1[currlen]; if(w1[cc[st+currlen]-'a']<0) w1[cc[st+currlen]-'a']+=mod1; --currlen; } currhash=0; REP(i,26) { w1[i]*=inversefactor1; w1[i]%=mod1; currhash+=w1[i]*perm[i][st+1]; currhash%=mod1; } if(currlen>1 && !hash.count(make_pair(currlen,currhash))) { hash[make_pair(currlen,currhash)]=actsimilar+1; } } vector<LL> vz(N),vv(N); REP(i,N) { if(i+v[i]<=N) vz[i+v[i]-1]++; } vv[0]=vz[0]; FOR(i,1,N) { vz[i]+=vz[i-1]; vv[i]=vv[i-1]+vz[i]; } REP(i,N) printf("%lldn",vv[i]); return 0;}Problem solution in C.#include <stdio.h> #include <stdlib.h> #include <string.h> struct range_minimum_query { int n; int **t; }; struct range_minimum_query * create_range_minimum_query( int n, int *a ) { int i; int j; struct range_minimum_query *rmq; if (n < 1) { fprintf(stderr, "ERROR: n < 1n"); exit(EXIT_FAILURE); } rmq = malloc(sizeof(struct range_minimum_query)); if (rmq == NULL) { fprintf(stderr, "ERROR: malloc failed.n"); exit(EXIT_FAILURE); } rmq->n = n; rmq->t = malloc(sizeof(int *) * n); if (rmq->t == NULL) { fprintf(stderr, "ERROR: malloc failed.n"); exit(EXIT_FAILURE); } j = 1; while ((1 << j) <= n) { j++; } for (i = 0; i < n; i++) { if ((i + (1 << (j - 1))) > n) { j--; } rmq->t[i] = malloc(sizeof(int) * j); if (rmq->t[i] == NULL) { fprintf(stderr, "ERROR: malloc failed.n"); exit(EXIT_FAILURE); } rmq->t[i][0] = a[i]; } for (j = 1; (1 << j) <= n; j++) { for (i = 0; (i + (1 << j)) <= n; i++) { if (rmq->t[i][j - 1] <= rmq->t[i + (1 << (j - 1))][j - 1]) { rmq->t[i][j] = rmq->t[i][j - 1]; } else { rmq->t[i][j] = rmq->t[i + (1 << (j - 1))][j - 1]; } } } return rmq; } void free_range_minimum_query( struct range_minimum_query *rmq ) { int i; for (i = 0; i < rmq->n; i++) { free(rmq->t[i]); } free(rmq->t); free(rmq); return; } int min_int( int x, int y ) { return ((x <= y) ? x : y); } int lookup_range_minimum_query( struct range_minimum_query *rmq, int i, int j ) { int k; if (i > j) { fprintf(stderr, "ERROR: i > jn"); exit(EXIT_FAILURE); } if (i == j) { return rmq->t[i][0]; } k = 0; for (;;) { if ((i + (1 << k) - 1) == j) { return rmq->t[i][k]; } if ((i + (1 << (k + 1)) - 1) > j) { return min_int(rmq->t[i][k], rmq->t[j - (1 << k) + 1][k]); } k++; } } #define ALPHABET_FIRST_CHAR 'a' #define ALPHABET_LAST_CHAR 'z' #define ALPHABET_SIZE (ALPHABET_LAST_CHAR - ALPHABET_FIRST_CHAR + 1) struct pseudo_isomorphic_suffix_array { int n; char *string; int *suffix_index; struct range_minimum_query *lcp_rmq; }; struct spanning_previous_links { int count; int array[ALPHABET_SIZE]; }; struct character_ranks_for_suffix { int rank[ALPHABET_SIZE]; }; struct pseudo_isomorphic_suffix_array_context { int n; char *string; int *distance_from_previous; struct spanning_previous_links *spanning_previous_links; struct character_ranks_for_suffix *character_ranks_for_suffix; int *index; int *temp; int *rank; int *lcp; struct range_minimum_query *lcp_rmq; int *group; int iteration; }; #if VERBOSE void print_int_array( char *prefix, int *a, int n ) { int i; fprintf(stderr, "%s", prefix); for (i = 0; i < n; i++) { fprintf(stderr, " %d", a[i]); } fprintf(stderr, "n"); return; } void print_pseudo_isomorphic_suffix_array_context( struct pseudo_isomorphic_suffix_array_context *ctx ) { fprintf(stderr, "INFO: CONTEXT: Iteration %dn", ctx->iteration); print_int_array("INFO: CONTEXT: index:", ctx->index, ctx->n); print_int_array("INFO: CONTEXT: rank:", ctx->rank, ctx->n); print_int_array("INFO: CONTEXT: lcp:", ctx->lcp, ctx->n); print_int_array("INFO: CONTEXT: group:", ctx->group, ctx->n); return; } #endif void initialize_pseudo_isomorphic_suffix_array_context( struct pseudo_isomorphic_suffix_array_context *ctx, char *s, int n ) { int i; int j; int k; int previous[ALPHABET_SIZE]; int sorted_by_next[ALPHABET_SIZE]; #if VERBOSE fprintf(stderr, "INFO: string:"); for (i = 0; i < n; i++) { fprintf(stderr, " %c", s[i]); } fprintf(stderr, "n"); #endif ctx->n = n; ctx->string = malloc(sizeof(char) * (n + 1)); if (ctx->string == NULL) { fprintf(stderr, "ERROR: malloc failed.n"); exit(EXIT_FAILURE); } memcpy(ctx->string, s, sizeof(char) * n); ctx->string[n] = 0; ctx->distance_from_previous = malloc(sizeof(int) * n); if (ctx->distance_from_previous == NULL) { fprintf(stderr, "ERROR: malloc failed.n"); exit(EXIT_FAILURE); } for (i = 0; i < ALPHABET_SIZE; i++) { previous[i] = -1; } for (i = 0; i < n; i++) { ctx->distance_from_previous[i] = i - previous[s[i] - ALPHABET_FIRST_CHAR]; previous[s[i] - ALPHABET_FIRST_CHAR] = i; } #if VERBOSE fprintf(stderr, "INFO: distance_from_previous:"); for (i = 0; i < n; i++) { fprintf(stderr, " %d", ctx->distance_from_previous[i]); } fprintf(stderr, "n"); #endif ctx->spanning_previous_links = malloc(sizeof(struct spanning_previous_links) * n); if (ctx->spanning_previous_links == NULL) { fprintf(stderr, "ERROR: malloc failed.n"); exit(EXIT_FAILURE); } for (i = 0; i < n; i++) { ctx->spanning_previous_links[i].count = 0; } for (i = 0; i < n; i++) { for (j = i - ctx->distance_from_previous[i]; j < i; j++) { if (j >= 0) { ctx->spanning_previous_links[j] .array[ctx->spanning_previous_links[j].count] = i; ctx->spanning_previous_links[j].count++; } } } #if VERBOSE for (i = 0; i < n; i++) { fprintf(stderr, "INFO: spanning_previous_links[%d]:", i); for (j = 0; j < ctx->spanning_previous_links[i].count; j++) { fprintf(stderr, " %d", ctx->spanning_previous_links[i].array[j]); } fprintf(stderr, "n"); } #endif ctx->character_ranks_for_suffix = malloc(sizeof(struct character_ranks_for_suffix) * n); if (ctx->character_ranks_for_suffix == NULL) { fprintf(stderr, "ERROR: malloc failed.n"); exit(EXIT_FAILURE); } for (i = 0; i < ALPHABET_SIZE; i++) { sorted_by_next[i] = i; } for (i = n - 1; i >= 0; i--) { j = s[i] - ALPHABET_FIRST_CHAR; k = 0; while (sorted_by_next[k] != j) { k++; } while (k > 0) { sorted_by_next[k] = sorted_by_next[k - 1]; k--; } sorted_by_next[0] = j; for (k = 0; k < ALPHABET_SIZE; k++) { ctx->character_ranks_for_suffix[i].rank[sorted_by_next[k]] = k; } } #if VERBOSE for (i = 0; i < n; i++) { fprintf(stderr, "INFO: character_ranks_for_suffix[%d]:", i); for (j = 0; j < ALPHABET_SIZE; j++) { fprintf(stderr, " %d", ctx->character_ranks_for_suffix[i].rank[j]); } fprintf(stderr, "n"); } #endif ctx->index = malloc(sizeof(int) * n); if (ctx->index == NULL) { fprintf(stderr, "ERROR: malloc failed.n"); exit(EXIT_FAILURE); } ctx->temp = malloc(sizeof(int) * n); if (ctx->temp == NULL) { fprintf(stderr, "ERROR: malloc failed.n"); exit(EXIT_FAILURE); } ctx->rank = malloc(sizeof(int) * n); if (ctx->rank == NULL) { fprintf(stderr, "ERROR: malloc failed.n"); exit(EXIT_FAILURE); } ctx->lcp = malloc(sizeof(int) * n); if (ctx->lcp == NULL) { fprintf(stderr, "ERROR: malloc failed.n"); exit(EXIT_FAILURE); } ctx->group = malloc(sizeof(int) * n); if (ctx->group == NULL) { fprintf(stderr, "ERROR: malloc failed.n"); exit(EXIT_FAILURE); } for (i = 0; i < n; i++) { ctx->index[i] = i; ctx->rank[i] = i; } for (i = 1; i < n; i++) { ctx->lcp[i] = 1; } ctx->lcp_rmq = create_range_minimum_query(n, ctx->lcp); for (i = 0; i < n; i++) { ctx->group[i] = 0; } ctx->iteration = 0; return; } int compute_lcp_in_pseudo_isomorphic_suffix_array_context( struct pseudo_isomorphic_suffix_array_context *ctx, int s1, int s2 ) { int i; int j; struct spanning_previous_links *spl; int ss1; int ss2; int x; int y; if (s1 == s2) { fprintf(stderr, "ERROR: s1 == s2n"); exit(EXIT_FAILURE); } if (ctx->group[s1] != ctx->group[s2]) { if (ctx->rank[s1] < ctx->rank[s2]) { i = ctx->rank[s1] + 1; j = ctx->rank[s2]; } else { i = ctx->rank[s2] + 1; j = ctx->rank[s1]; } return lookup_range_minimum_query(ctx->lcp_rmq, i, j); } x = 1 << ctx->iteration; ss1 = s1 + x; ss2 = s2 + x; if ((ss1 >= ctx->n) || (ss2 >= ctx->n)) { return x; } if (ctx->group[ss1] == ctx->group[ss2]) { y = x + x; } else { if (ctx->rank[ss1] < ctx->rank[ss2]) { i = ctx->rank[ss1] + 1; j = ctx->rank[ss2]; } else { i = ctx->rank[ss2] + 1; j = ctx->rank[ss1]; } y = x + lookup_range_minimum_query(ctx->lcp_rmq, i, j); } spl = &ctx->spanning_previous_links[ss1 - 1]; for (i = 0; i < spl->count; i++) { j = spl->array[i]; if (j >= (s1 + y)) { break; } if (((j - ctx->distance_from_previous[j]) >= s1) && (ctx->distance_from_previous[j] != ctx->distance_from_previous[s2 + (j - s1)]) ) { y = j - s1; break; } } spl = &ctx->spanning_previous_links[ss2 - 1]; for (i = 0; i < spl->count; i++) { j = spl->array[i]; if (j >= (s2 + y)) { break; } if (((j - ctx->distance_from_previous[j]) >= s2) && (ctx->distance_from_previous[j] != ctx->distance_from_previous[s1 + (j - s2)]) ) { y = j - s2; break; } } return y; } int compare_suffix_in_pseudo_isomorphic_suffix_array_context( struct pseudo_isomorphic_suffix_array_context *ctx, int s1, int s2 ) { char c1; char c2; int lcp; int r1; int r2; int ss1; int ss2; if (s1 == s2) { fprintf(stderr, "ERROR: s1 == s2n"); exit(EXIT_FAILURE); } lcp = compute_lcp_in_pseudo_isomorphic_suffix_array_context(ctx, s1, s2); ss1 = s1 + lcp; ss2 = s2 + lcp; if (ss1 >= ctx->n) { return -1; } if (ss2 >= ctx->n) { return 1; } c1 = ctx->string[ss1]; c2 = ctx->string[ss2]; r1 = ctx->character_ranks_for_suffix[s1].rank[c1 - ALPHABET_FIRST_CHAR]; r2 = ctx->character_ranks_for_suffix[s2].rank[c2 - ALPHABET_FIRST_CHAR]; return r1 - r2; } void run_merge_sort_in_pseudo_isomorphic_suffix_array_context( struct pseudo_isomorphic_suffix_array_context *ctx, int l, int r ) { int i; int j; int k; int m; int t; if (l > r) { fprintf(stderr, "ERROR: l > rn"); exit(EXIT_FAILURE); } if (l == r) { return; } if ((l + 1) == r) { if (compare_suffix_in_pseudo_isomorphic_suffix_array_context( ctx, ctx->index[l], ctx->index[r]) <= 0) { return; } t = ctx->index[l]; ctx->index[l] = ctx->index[r]; ctx->index[r] = t; return; } m = (l + r) >> 1; run_merge_sort_in_pseudo_isomorphic_suffix_array_context(ctx, l, m - 1); run_merge_sort_in_pseudo_isomorphic_suffix_array_context(ctx, m, r); i = l; j = m; k = l; while ((i < m) && (j <= r)) { if (compare_suffix_in_pseudo_isomorphic_suffix_array_context( ctx, ctx->index[i], ctx->index[j]) <= 0) { ctx->temp[k] = ctx->index[i]; i++; } else { ctx->temp[k] = ctx->index[j]; j++; } k++; } while (i < m) { ctx->temp[k] = ctx->index[i]; i++; k++; } while (j <= r) { ctx->temp[k] = ctx->index[j]; j++; k++; } for (k = l; k <= r; k++) { ctx->index[k] = ctx->temp[k]; } return; } void update_lcps_in_pseudo_isomorphic_suffix_array_context( struct pseudo_isomorphic_suffix_array_context *ctx ) { int i; for (i = 1; i < ctx->n; i++) { ctx->lcp[i] = compute_lcp_in_pseudo_isomorphic_suffix_array_context( ctx, ctx->index[i - 1], ctx->index[i]); } free_range_minimum_query(ctx->lcp_rmq); ctx->lcp_rmq = create_range_minimum_query(ctx->n, ctx->lcp); return; } void update_ranks_in_pseudo_isomorphic_suffix_array_context( struct pseudo_isomorphic_suffix_array_context *ctx ) { int i; int j; for (i = 0; i < ctx->n; i++) { j = ctx->index[i]; ctx->rank[j] = i; } return; } void update_groups_in_pseudo_isomorphic_suffix_array_context( struct pseudo_isomorphic_suffix_array_context *ctx ) { int group_index; int i; int max_lcp; group_index = 0; max_lcp = 1 << ctx->iteration; ctx->group[ctx->index[0]] = group_index; for (i = 1; i < ctx->n; i++) { if (ctx->lcp[i] != max_lcp) { group_index++; } ctx->group[ctx->index[i]] = group_index; } return; } struct pseudo_isomorphic_suffix_array * create_pseudo_isomorphic_suffix_array_from_context( struct pseudo_isomorphic_suffix_array_context *ctx ) { struct pseudo_isomorphic_suffix_array *pisa; pisa = malloc(sizeof(struct pseudo_isomorphic_suffix_array)); if (pisa == NULL) { fprintf(stderr, "ERROR: malloc failed.n"); exit(EXIT_FAILURE); } pisa->n = ctx->n; pisa->string = ctx->string; pisa->suffix_index = ctx->index; pisa->lcp_rmq = ctx->lcp_rmq; free(ctx->distance_from_previous); free(ctx->spanning_previous_links); free(ctx->character_ranks_for_suffix); free(ctx->temp); free(ctx->rank); free(ctx->lcp); free(ctx->group); return pisa; } struct pseudo_isomorphic_suffix_array * create_pseudo_isomorphic_suffix_array( char *s, int n ) { struct pseudo_isomorphic_suffix_array_context ctx; int i; if (n < 1) { fprintf(stderr, "ERROR: n < 1n"); exit(EXIT_FAILURE); } for (i = 0; i < n; i++) { if ((s[i] < ALPHABET_FIRST_CHAR) || (s[i] > ALPHABET_LAST_CHAR)){ fprintf(stderr, "ERROR: %c is not in the supported alphabet.n", s[i]); exit(EXIT_FAILURE); } } initialize_pseudo_isomorphic_suffix_array_context(&ctx, s, n); #if VERBOSE print_pseudo_isomorphic_suffix_array_context(&ctx); #endif while ((1 << ctx.iteration) < n) { run_merge_sort_in_pseudo_isomorphic_suffix_array_context(&ctx, 0, n - 1); update_lcps_in_pseudo_isomorphic_suffix_array_context(&ctx); update_ranks_in_pseudo_isomorphic_suffix_array_context(&ctx); ctx.iteration++; update_groups_in_pseudo_isomorphic_suffix_array_context(&ctx); #if VERBOSE print_pseudo_isomorphic_suffix_array_context(&ctx); #endif } return create_pseudo_isomorphic_suffix_array_from_context(&ctx); } void free_pseudo_isomorphic_suffix_array( struct pseudo_isomorphic_suffix_array *pisa ) { free(pisa->string); free(pisa->suffix_index); free_range_minimum_query(pisa->lcp_rmq); free(pisa); return; } long * get_lcp_sums_by_suffix_length( char *s, int n ) { int i; int j; long *lcp_sum; int *next; struct pseudo_isomorphic_suffix_array *pisa; int *prev; int *rank; int sl; long x; int y; lcp_sum = malloc(sizeof(long) * n); if (lcp_sum == NULL) { fprintf(stderr, "ERROR: malloc failed.n"); exit(EXIT_FAILURE); } rank = malloc(sizeof(int) * n); if (rank == NULL) { fprintf(stderr, "ERROR: malloc failed.n"); exit(EXIT_FAILURE); } prev = malloc(sizeof(int) * n); if (prev == NULL) { fprintf(stderr, "ERROR: malloc failed.n"); exit(EXIT_FAILURE); } next = malloc(sizeof(int) * n); if (next == NULL) { fprintf(stderr, "ERROR: malloc failed.n"); exit(EXIT_FAILURE); } pisa = create_pseudo_isomorphic_suffix_array(s, n); for (i = 0; i < n; i++) { j = pisa->suffix_index[i]; rank[j] = i; prev[j] = ((i == 0) ? -1 : pisa->suffix_index[i - 1]); next[j] = ((i == (n - 1)) ? -1 : pisa->suffix_index[i + 1]); } x = 0; for (i = 0; i < n; i++) { x += pisa->lcp_rmq->t[i][0]; } lcp_sum[n - 1] = x; for (sl = n - 1; sl > 0; sl--) { i = n - 1 - sl; if (prev[i] != -1) { y = lookup_range_minimum_query(pisa->lcp_rmq, rank[prev[i]] + 1, rank[i]); x -= y; } if (next[i] != -1) { y = lookup_range_minimum_query(pisa->lcp_rmq, rank[i] + 1, rank[next[i]]); x -= y; } if ((prev[i] != -1) && (next[i] != -1)) { y = lookup_range_minimum_query(pisa->lcp_rmq, rank[prev[i]] + 1, rank[next[i]]); x += y; } if (prev[i] != -1) { next[prev[i]] = next[i]; } if (next[i] != -1) { prev[next[i]] = prev[i]; } lcp_sum[sl - 1] = x; } free_pseudo_isomorphic_suffix_array(pisa); free(rank); free(prev); free(next); return lcp_sum; } void reverse( char *s, int n ) { int l; int r; char t; l = 0; r = n - 1; while (l < r) { t = s[l]; s[l] = s[r]; s[r] = t; l++; r--; } return; } void run( char *s, int n ) { int l; long *lcp_sum; long x; reverse(s, n); lcp_sum = get_lcp_sums_by_suffix_length(s, n); x = 0; for (l = 1; l <= n; l++) { x += l; printf("%ldn", x - lcp_sum[l - 1]); } return; } int main( int argc, char **argv ) { char *s; s = malloc(sizeof(char) * (1024 * 1024)); scanf("%s", s); run(s, strlen(s)); return 0; } Algorithms coding problems solutions AlgorithmsHackerRank