In this HackerRank String Function Calculation problem solution, we have given a string t and a value of string s over function f and it can be calculated as f(s) = |s| x Number of times s occurs in the t and we need to find out the maximum value of f(s) among all the substrings (s) of string t.
Problem solution in Python.
#!/bin/python3
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()
Problem solution in Java.
import java.util.Arrays;
import java.util.ArrayDeque;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.awt.Point;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.Comparator;
import java.io.FileReader;
import java.io.IOException;
import java.util.StringTokenizer;
class StringCal {
static class Node {
static int[] a;
final static int neg = -1;
final int start;
final int end;
final int min;
Node[] nodes;
public Node(int start, int end) {
this.start = start;
this.end = end;
if (start < end) {
int min = neg;
int[] pos = {start, (start + end) / 2, end};
nodes = new Node[2];
for (int i = 0; i < 2; i++) {
nodes[i] = new Node(pos[i] + i, pos[i + 1]);
if (min == -1 || a[nodes[i].min] < a[min]) {
min = nodes[i].min;
}
}
this.min = min;
} else {
min = start;
}
}
public int query(int queryStart, int queryEnd) {
if (queryEnd < start || end < queryStart) {
return neg;
}
if (queryStart <= start && end <= queryEnd) {
return min;
}
int ans = neg;
for (Node node: nodes) {
int temp = node.query(queryStart, queryEnd);
if (temp > neg && (ans == neg || a[temp] < a[ans])) {
ans = temp;
}
}
return ans;
}
}
public void solve(int testNumber, InputReader in, OutputWriter out) {
String s = in.next();
int[] lcp = XString.lcp(s);
Node.a = lcp;
Node root = new Node(0, lcp.length - 2);
ArrayDeque<Point> stack = new ArrayDeque<>();
stack.push(new Point(0, lcp.length - 2));
long ans = s.length();
while (!stack.isEmpty()) {
Point point = stack.pop();
int start = point.x;
int end = point.y;
if (start <= end) {
int min = root.query(start, end);
ans = Math.max(ans, (long)lcp[min] * (end - start + 2));
stack.push(new Point(start, min - 1));
stack.push(new Point(min + 1, end));
}
}
out.println(ans);
}
}
class InputReader {
private BufferedReader input;
private StringTokenizer line = new StringTokenizer("");
public InputReader(InputStream in) {
input = new BufferedReader(new InputStreamReader(in));
}
public void fill() {
try {
if(!line.hasMoreTokens()) line = new StringTokenizer(input.readLine());
} catch(IOException io) { io.printStackTrace(); System.exit(0);}
}
public String next() {
fill();
return line.nextToken();
}
}
class OutputWriter {
private PrintWriter output;
public OutputWriter(OutputStream out) {
output = new PrintWriter(out);
}
public void println(Object o) {
output.println(o);
}
public void close() {
output.close();
}
}
class XString {
public static int[] lcp(String str, int[] suffix) {
final int n = str.length();
int[] pos = new int[n];
for (int i = 0; i < n; i++) {
pos[suffix[i]] = i;
}
int[] lcp = new int[n];
for (int i = 0, w = 0; i < n; i++) {
if (pos[i] < n - 1) {
int j = suffix[pos[i] + 1];
while (Math.max(i, j) + w < n && str.charAt(i + w) == str.charAt(j + w)) {
w++;
}
lcp[pos[i]] = w;
if (w > 0) {
w--;
}
}
}
return lcp;
}
public static int[] lcp(String str) {
int[] suffix = suffixArray(str);
return lcp(str, suffix);
}
public static int[] suffixArray(String str) {
final int n = str.length();
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) {
order[i] = n - i - 1;
}
Arrays.sort(order, (a, b) -> str.charAt(a) - str.charAt(b));
int[] suffix = new int[n];
int[] rank = new int[n];
for (int i = 0; i < n; i++) {
suffix[i] = order[i];
rank[suffix[i]] = str.charAt(suffix[i]);
}
for (int len = 1; len < n; len <<= 1) {
int[] r = Arrays.copyOf(rank, n);
for (int i = 0; i < n; i++) {
if (i > 0 && r[suffix[i - 1]] == r[suffix[i]] &&
suffix[i - 1] + len < n &&
r[suffix[i - 1] + len / 2] == r[suffix[i] + len / 2]) {
rank[suffix[i]] = rank[suffix[i - 1]];
} else {
rank[suffix[i]] = i;
}
}
int[] pos = new int[n];
for (int i = 0; i < n; i++) {
pos[i] = i;
}
int[] s = Arrays.copyOf(suffix, n);
for (int i = 0; i < n; i++) {
int t = s[i] - len;
if (t >= 0) {
suffix[pos[rank[t]]++] = t;
}
}
}
return suffix;
}
}
public class Solution {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
StringCal solver = new StringCal();
solver.solve(1, in, out);
out.close();
}
}
Problem solution in C++.
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stack>
using namespace std;
#define maxn 100010
int wa[maxn] = {};
int wb[maxn] = {};
int wv[maxn] = {};
int height[maxn] = {};
char ss[maxn] = {};
int r[maxn] = {};
int sa[maxn] = {};
int wws[maxn] = {};
int rrank[maxn] = {};
int cmp(int *r,int a,int b,int l) {
return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(int *r,int *sa,int n,int m) {
int i,j,p,*x=wa,*y=wb,*t;
for(i=0;i<m;i++) wws[i]=0;
for(i=0;i<n;i++) wws[x[i]=r[i]]++;
for(i=1;i<m;i++) wws[i]+=wws[i-1];
for(i=n-1;i>=0;i--) sa[--wws[x[i]]]=i;
for(j=1,p=1;p<n;j*=2,m=p) {
for(p=0,i=n-j;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=0;i<n;i++) wv[i]=x[y[i]];
for(i=0;i<m;i++) wws[i]=0;
for(i=0;i<n;i++) wws[wv[i]]++;
for(i=1;i<m;i++) wws[i]+=wws[i-1];
for(i=n-1;i>=0;i--) sa[--wws[wv[i]]]=y[i];
for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
return;
}
void calheight(int *r,int *sa,int n) {
int i,j,k=0;
for(i=1;i<=n;i++) rrank[sa[i]]=i;
for(i=0;i<n;height[rrank[i++]]=k)
for(k?k--:0,j=sa[rrank[i]-1];r[i+k]==r[j+k];k++);
return;
}
int find(int n) {
stack<int> s;
int res = 0;
for(int i = 1; i <= n; i++) {
while(!s.empty()&&height[s.top()] > height[i]) {
int h = height[s.top()];
s.pop();
int index = s.empty()?0:s.top();
res = max(res, (i-index)*h);
}
s.push(i);
}
return res;
}
int main() {
int t = scanf("%s", ss);
int l = strlen(ss);
for(int i = 0; i < l; i++) {
r[i] = ss[i]-'a'+1;
}
da(r, sa, l+1, 27);
calheight(r, sa, l);
printf("%d\n", max(find(l+1), l));
return 0;
}
Problem solution in C.
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define MAXN 100000+2
char str[MAXN];
int sa[MAXN];
int rank[MAXN];
int cnt[MAXN];
int wb[MAXN];
int wv[MAXN];
int height[MAXN];
int stack[MAXN];
inline int max(int a, int b) {
return a > b? a : b;
}
int cmp(int *r, int a, int b, int k) {
return r[a] == r[b] && r[a+k] == r[b+k];
}
void gen_sa(char *str, int n, int *sa, int *rank) {
int m = 128, p;
int i, j, k;
int *x, *y, *t;
x = rank; y = wb;
memset(cnt, 0, sizeof(int) * m);
for (i = 0; i < n; ++ i) ++ cnt[x[i] = str[i]];
for (i = 1; i < m; ++ i) cnt[i] += cnt[i-1];
for (i = n-1; i >= 0; -- i) sa[--cnt[x[i]]] = i;
for (k = 1; k <= n; k = k << 1) {
for (p = 0, i = n-k; i < n; ++ i) y[p++] = i;
for (i = 0; i < n; ++ i) if (sa[i] >= k) y[p++] = sa[i] - k;
memset(cnt, 0, sizeof(int) * m);
for (i = 0; i < n; ++ i) {
wv[i] = x[y[i]];
++ cnt[wv[i]];
}
for (i = 1; i < m; ++ i) cnt[i] += cnt[i-1];
for (i = n-1; i >= 0; -- i) sa[--cnt[wv[i]]] = y[i];
t = x; x = y; y = t;
x[sa[0]] = 0;
for (p = 1, i = 0; i < n; ++ i) {
x[sa[i]] = cmp(y, sa[i], sa[i-1], k) ? p-1: p++;
}
m = p;
}
if (x != rank) memcpy(rank, x, sizeof(int)*n);
}
void gen_height(char *str, int n, int *sa, int *rank, int *height) {
int i, j, k;
height[0] = 0;
k = 0;
for (i = 0; i < n-1; ++ i) {
if (k) -- k;
j = rank[i]-2;
if (j == -1) continue;
for (j = sa[j]; str[i+k] == str[j+k]; ) {
++ k;
}
height[rank[i]-1] = k;
}
}
int max_rectangle(int *height, int n) {
int i, j, left, right, cur, top = -1;
int result = 0;
height[n] = 0;
stack[++top] = 0;
for (i = 0; i <= n; ++ i) {
while (top > -1 && height[i] < height[stack[top]]) {
cur = stack[top--];
left = (top > -1? cur-stack[top]: cur+1) * height[cur];
right = (i - cur - 1) * height[cur];
result = max(result, left+right+height[cur]);
}
stack[++top] = i;
}
return max(result, n-1);
}
int main() {
int n, result;
scanf("%s", str);
n = strlen(str);
gen_sa(str, n+1, sa, rank);
gen_height(str, n+1, sa, rank, height);
result = max_rectangle(height, n+1);
printf("%d\n", result);
return 0;
}
0 Comments