# String Function Calculation – HackerRank Solution

In this post, we will solve String Function Calculation HackerRank Solution. This problem (String Function Calculation) is a part of HackerRank Problem Solving series.

Contents

## String Function Calculation – HackerRank Solution

### C++

```#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

#define nb nexta
#define rank b

const int maxn = 100010;
char s[maxn];
int n, id[maxn], height[maxn], b[maxn], nexta[maxn];

bool cmp(const int& i, const int& j)
{
return s[i] < s[j];
}

void SuffixSort()
{
int i, j, k, h;
for (i = 0; i < n; i++) id[i] = i;
sort(id, id + n, cmp);
for (i = 0; i < n; i++)
{
if (i == 0 || s[id[i]] != s[id[i - 1]])
b[id[i]] = i;
else b[id[i]] = b[id[i - 1]];
}
for (h = 1; h < n; h <<= 1)
{
for (i = 0; i < n; i++)
for (i = n - 1; i >= 0; i--)
{
if (id[i])
{
j = id[i] - h;
if (j < 0) j += n;
}
}
j = n - h;
for (i = k = 0; i < n; i++)
for (j = head[i]; j >= 0; j = nexta[j])
id[k++] = j;
for (i = 0; i < n; i++)
if (i>0 && id[i] + h < n&&id[i - 1] + h < n&&b[id[i]] == b[id[i - 1]] && b[id[i] + h] == b[id[i - 1] + h])
nb[id[i]] = nb[id[i - 1]];
else
nb[id[i]] = i;
for (i = 0; i < n; i++)
b[i] = nb[i];
}
}

void GetHeight()
{
int i, j, h; height[0] = 0;
for (i = 0; i < n; i++)
rank[id[i]] = i;
for (h = 0, i = 0; i < n; i++)
{
if (rank[i] > 0)
{
j = id[rank[i] - 1];
while (s[i + h] == s[j + h])++h;
height[rank[i]] = h;
if (h>0) --h;
}
}
}

int st[maxn], top;

int main()
{
cin >> s;
n = strlen(s);
top = 0;
SuffixSort();
GetHeight();
height[n] = 0;
int best = n;
st[top++] = 0;
for (int i = 1; i < n + 1; i++)
{
//cout << height[i] << " ";
while (top != 0 && height[i] < height[st[top - 1]])
{
int val = height[st[top - 1]];
top--;
best = max(best, val * (top == 0 ? i : i - st[top - 1]));
}

if (top == 0 || height[i] >= height[st[top - 1]])
st[top++] = i;
}
cout << best << endl;
return 0;
}
```

### Python

```import os
from itertools import zip_longest, islice

def suffix_array_best(s):
"""
suffix array of s
O(n * log(n)^2)
"""
n = len(s)
k = 1
line = to_int_keys_best(s)
while max(line) < n - 1:
line = to_int_keys_best(
[a * (n + 1) + b + 1
for (a, b) in
zip_longest(line, islice(line, k, None),
fillvalue=-1)])
k <<= 1
return line

def inverse_array(l):
n = len(l)
ans = [0] * n
for i in range(n):
ans[l[i]] = i
return ans

def to_int_keys_best(l):
seen = set()
ls = []
for e in l:
if not e in seen:
ls.append(e)
ls.sort()
index = {v: i for i, v in enumerate(ls)}
return [index[v] for v in l]

def suffix_matrix_best(s):
n = len(s)
k = 1
line = to_int_keys_best(s)
ans = [line]
while max(line) < n - 1:
line = to_int_keys_best(
[a * (n + 1) + b + 1
for (a, b) in
zip_longest(line, islice(line, k, None), fillvalue=-1)])
ans.append(line)
k <<= 1
return ans

def suffix_array_alternative_naive(s):
return [rank for suffix, rank in sorted((s[i:], i) for i in range(len(s)))]

def lcp(sm, i, j):
n = len(sm[-1])
if i == j:
return n - i
k = 1 << (len(sm) - 2)
ans = 0
for line in sm[-2::-1]:
if i >= n or j >= n:
break
if line[i] == line[j]:
ans ^= k
i += k
j += k
k >>= 1
return ans

def maxValue(a):
res = inverse_array(suffix_array_best(a))
# res = suffix_array_alternative_naive(a)

mtx = suffix_matrix_best(a)

lcp_res = []
for n in range(len(res) - 1):
lcp_res.append(lcp(mtx, res[n], res[n+1]))
lcp_res.append(0)

max_score = len(a)

lcp_res_len = len(lcp_res)

for i, num in enumerate(res):

if lcp_res[i] <= 1:
continue

lcp_res_i = lcp_res[i]

cnt = 2
for ii in range(i+1, lcp_res_len):
if lcp_res[ii] >= lcp_res_i:
cnt += 1
else:
break
for ii in range(i-1, -1, -1):
if lcp_res[ii] >= lcp_res_i:
cnt += 1
else:
break

max_score = max(cnt * lcp_res_i, max_score)

return max_score

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

t = input()

result = maxValue(t)

fptr.write(str(result) + '\n')

fptr.close()
```

### Java

```package com.nastra.hackerrank.weekly;

import java.io.InputStream;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class StringFunctionCalculation {
public static long solve(String str) {
SuffixAutomata a = new SuffixAutomata(str);
return a.root.dp();
}

public static void main(String[] args) throws Exception {
FastScanner sc = new FastScanner(System.in);
String str = sc.next();
System.out.println(solve(str));
}

private static class SuffixAutomata {
private Vertex root;
private Vertex last;

private class Vertex {
Vertex[] edges;
int log = 0;
boolean visited = false;
int terminals = 0;

public Vertex(Vertex o, int log) {
edges = o.edges.clone();
this.log = log;
}

public Vertex(int log) {
edges = new Vertex[26];
this.log = log;
}

long dp() {
if (visited) {
return 0;
}
visited = true;
long r = 0;
for (Vertex v : edges) {
if (v != null) {
r = Math.max(r, v.dp());
terminals += v.terminals;
}
}
return Math.max(r, 1L * log * terminals);
}
}

public SuffixAutomata(String str) {
last = root = new Vertex(0);
for (int i = 0; i < str.length(); i++) {
}
}

Vertex cur = last;
last = new Vertex(cur.log + 1);
while (cur != null && cur.edges[c - 'a'] == null) {
cur.edges[c - 'a'] = last;
}
if (cur != null) {
Vertex q = cur.edges[c - 'a'];
if (q.log == cur.log + 1) {
} else {
Vertex r = new Vertex(q, cur.log + 1);
while (cur != null) {
if (cur.edges[c - 'a'] == q) {
cur.edges[c - 'a'] = r;
} else {
break;
}
}
}
} else {
}
}

Vertex cur = last;
while (cur != null) {
cur.terminals++;
}
}
}

static class FastScanner {

private static StringTokenizer tokenizer;

public FastScanner(InputStream in) throws Exception {
}

public int numTokens() throws Exception {
if (!tokenizer.hasMoreTokens()) {
return numTokens();
}
}

public boolean hasNext() throws Exception {
if (!tokenizer.hasMoreTokens()) {
return hasNext();
}
return true;
}

public String next() throws Exception {
if (!tokenizer.hasMoreTokens()) {
return next();
}
}

public double nextDouble() throws Exception {
return Double.parseDouble(next());
}

public float nextFloat() throws Exception {
return Float.parseFloat(next());
}

public long nextLong() throws Exception {
return Long.parseLong(next());
}

public int nextInt() throws Exception {
return Integer.parseInt(next());
}

public int[] nextIntArray() throws Exception {
int[] out = new int[line.length];
for (int i = 0; i < line.length; i++) {
out[i] = Integer.valueOf(line[i]);
}
return out;
}

public double[] nextDoubleArray() throws Exception {
double[] out = new double[line.length];
for (int i = 0; i < line.length; i++) {
out[i] = Double.valueOf(line[i]);
}
return out;
}

public Integer[] nextIntegerArray() throws Exception {
Integer[] out = new Integer[line.length];
for (int i = 0; i < line.length; i++) {
out[i] = Integer.valueOf(line[i]);
}
return out;
}

public BigInteger[] nextBigIngtegerArray() throws Exception {
BigInteger[] out = new BigInteger[line.length];
for (int i = 0; i < line.length; i++) {
out[i] = new BigInteger(line[i]);
}
return out;
}

public BigInteger nextBigInteger() throws Exception {
return new BigInteger(next());
}

public String nextLine() throws Exception {
}

public long[] nextLongArray() throws Exception {