In this post, we will solve String Function Calculation HackerRank Solution. This problem (String Function Calculation) is a part of HackerRank Problem Solving series.
String Function Calculation – HackerRank Solution
C++
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define nb nexta
#define head height
#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++)
head[i] = nexta[i] = -1;
for (i = n - 1; i >= 0; i--)
{
if (id[i])
{
j = id[i] - h;
if (j < 0) j += n;
nexta[j] = head[b[j]];
head[b[j]] = j;
}
}
j = n - h;
nexta[j] = head[b[j]];
head[b[j]] = j;
for (i = k = 0; i < n; i++)
if (head[i] >= 0)
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)
seen.add(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.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
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 suffixLink = null;
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++) {
addChar(str.charAt(i));
}
addTerminal();
}
private void addChar(char c) {
Vertex cur = last;
last = new Vertex(cur.log + 1);
while (cur != null && cur.edges[c - 'a'] == null) {
cur.edges[c - 'a'] = last;
cur = cur.suffixLink;
}
if (cur != null) {
Vertex q = cur.edges[c - 'a'];
if (q.log == cur.log + 1) {
last.suffixLink = q;
} else {
Vertex r = new Vertex(q, cur.log + 1);
r.suffixLink = q.suffixLink;
q.suffixLink = r;
last.suffixLink = r;
while (cur != null) {
if (cur.edges[c - 'a'] == q) {
cur.edges[c - 'a'] = r;
} else {
break;
}
cur = cur.suffixLink;
}
}
} else {
last.suffixLink = root;
}
}
private void addTerminal() {
Vertex cur = last;
while (cur != null) {
cur.terminals++;
cur = cur.suffixLink;
}
}
}
static class FastScanner {
private static BufferedReader reader;
private static StringTokenizer tokenizer;
public FastScanner(InputStream in) throws Exception {
reader = new BufferedReader(new InputStreamReader(in));
tokenizer = new StringTokenizer(reader.readLine().trim());
}
public int numTokens() throws Exception {
if (!tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine().trim());
return numTokens();
}
return tokenizer.countTokens();
}
public boolean hasNext() throws Exception {
if (!tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine().trim());
return hasNext();
}
return true;
}
public String next() throws Exception {
if (!tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine().trim());
return next();
}
return tokenizer.nextToken();
}
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 {
String[] line = reader.readLine().trim().split(" ");
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 {
String[] line = reader.readLine().trim().split(" ");
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 {
String[] line = reader.readLine().trim().split(" ");
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 {
String[] line = reader.readLine().trim().split(" ");
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 {
return reader.readLine().trim();
}
public long[] nextLongArray() throws Exception {
String[] line = reader.readLine().trim().split(" ");
long[] out = new long[line.length];
for (int i = 0; i < line.length; i++) {
out[i] = Long.valueOf(line[i]);
}
return out;
}
}
}
Note: This problem (String Function Calculation) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.