HackerRank String Function Calculation problem solution

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("%dn", 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("%dn", result);
    return 0;
}