HackerRank Pseudo-Isomorphic Substrings
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…
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)
