HackerRank Pseudo-Isomorphic Substrings

Yashwant Parihar,

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 = abcde
then, 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
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

Leave a Reply

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