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