HackerRank String Function Calculation Solution Yashwant Parihar, April 30, 2023May 6, 2023 In this post, we will solve HackerRank String Function Calculation Problem Solution. Jane loves strings more than anything. She has a string t with her, and value of strings over function f can be calculated as given below:f(s) = sx Number of times s occurs in tJane wants to know the maximum value of f(s) among all the substrings ($) of string t.Can you help her?Input FormatA single line containing string t.Output FormatPrint the maximum value of f(s) among all the substrings ($) of string t. Sample Input 0 aaaaaa Sample Output 0 12 Explanation 0 f('a') = 6 f('aa') = 10 f('aaa') = 12 f('aaaa') = 12 f('aaaaa') = 10 f('aaaaaa') = 6 Sample Input 1 abcabcddd Sample Output 1 9 Explanation 1 f values of few of the substrings are shown below: f("a") = 2 f("b") = 2 f("c") = 2 f("ab") = 4 f("bc") = 4 f("ddd") = 3 f("abc") = 6 f("abcabcddd") = 9 Among the function values 9 is the maximum one. HackerRank String Function Calculation Problem Solution String Function Calculation C Solution #include <stdio.h> #include <stdlib.h> #include <string.h> #define NN 100001 typedef struct _node{ int u; int w; } node; void heap_insert(node *heap,node *elem,int *size,int *heap_list); void heap_update(node *heap,node *elem,int size,int *heap_list); int init( int n ,int *N,int *tree); void range_increment( int i, int j, int val ,int N,int *tree); int query( int i ,int N,int *tree); void sort_a2(int*a,int*b,int size); void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size); void merge(int*a,int*left,int*right,int left_size, int right_size); void sort_a(int*a,int size); void suffixSort(int n); void LCP(int n); char str[NN]; //input int rank[NN], pos[NN], lcp[NN]; //output int cnt[NN], next[NN]; //internal int bh[NN], b2h[NN]; int main(){ scanf("%s",str); int len,i,c=0,heap_size=0,group,N,diff,tmax; int *index,*p,*u,*v,*ans,*tree; node *heap,temp; long long max=-1; len=strlen(str); suffixSort(len); LCP(len); index=(int*)malloc(len*sizeof(int)); p=(int*)malloc(len*sizeof(int)); u=(int*)malloc(len*sizeof(int)); v=(int*)malloc(len*sizeof(int)); ans=(int*)malloc(len*sizeof(int)); tree=(int*)malloc(3*len*sizeof(int)); heap=(node*)malloc(2*len*sizeof(node)); for(i=0;i<len;i++) index[i]=i; sort_a2(lcp,index,len); u[0]=0; v[0]=len-1; temp.u=0; temp.w=len; c++; init(len,&N,tree); heap_insert(heap,&temp,&heap_size,p); for(i=0;i<len;i++){ if(i && lcp[i]!=lcp[i-1]) ans[lcp[i-1]]=heap[1].w; group=query(index[i]+1,N,tree); temp.u=group; temp.w=v[group]-index[i]; u[c]=u[group]; u[group]=index[i]+1; heap_update(heap,&temp,heap_size,p); if(index[i]!=u[c]){ v[c]=index[i]-1; temp.u=c; temp.w=index[i]-u[c]; heap_insert(heap,&temp,&heap_size,p); diff=c-group; range_increment(u[c]+1,v[c]+1,diff,N,tree); c++; } } ans[lcp[i-1]]=heap[1].w; tmax=len-1; for(i=0;i<len;i++) if(ans[i]==-1) ans[i]=tmax; else tmax=ans[i]; for(i=0;i<len;i++) if(max==-1 || (ans[i]+1)*(long long)(i+1)>max) max=(ans[i]+1)*(long long)(i+1); printf("%lld",max); return 0; } void heap_insert(node *heap,node *elem,int *size,int *heap_list){ (*size)++; int index=(*size); while(index>1 && elem->w>heap[index/2].w){ heap[index]=heap[index/2]; heap_list[heap[index].u]=index; index/=2; } heap[index]=(*elem); heap_list[elem->u]=index; return; } void heap_update(node *heap,node *elem,int size,int *heap_list){ int index=heap_list[elem->u]; int max,maxi; while(1){ if(2*index<=size){ max=heap[2*index].w; maxi=2*index; } else break; if(2*index+1<=size && heap[2*index+1].w>max){ max=heap[2*index+1].w; maxi=2*index+1; } if(elem->w<max){ heap[index]=heap[maxi]; heap_list[heap[index].u]=index; index=maxi; } else break; } heap[index]=(*elem); heap_list[elem->u]=index; return; } // initialises a tree for n data entries int init( int n ,int *N,int *tree) { (*N) = 1; while( (*N) < n ) (*N) *= 2; int i; for( i = 1; i < (*N) + n; i++ ) tree[i] = 0; return 0; } // increments a[k] by val for all k between i and j, inclusive void range_increment( int i, int j, int val ,int N,int *tree) { for( i += N, j += N; i <= j; i = ( i + 1 ) / 2, j = ( j - 1 ) / 2 ) { if( i % 2 == 1 ) tree[i] += val; if( j % 2 == 0 ) tree[j] += val; } } // compute a[i] int query( int i ,int N,int *tree) { int ans = 0,j; for( j = i + N; j; j /= 2 ) ans += tree[j]; return ans; } void sort_a2(int*a,int*b,int size) { if (size < 2) return; int m = (size+1)/2,i; int*left_a,*left_b,*right_a,*right_b; left_a=(int*)malloc(m*sizeof(int)); right_a=(int*)malloc((size-m)*sizeof(int)); left_b=(int*)malloc(m*sizeof(int)); right_b=(int*)malloc((size-m)*sizeof(int)); for(i=0;i<m;i++){ left_a[i]=a[i]; left_b[i]=b[i]; } for(i=0;i<size-m;i++){ right_a[i]=a[i+m]; right_b[i]=b[i+m]; } sort_a2(left_a,left_b,m); sort_a2(right_a,right_b,size-m); merge2(a,left_a,right_a,b,left_b,right_b,m,size-m); free(left_a); free(right_a); free(left_b); free(right_b); return; } void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size) { int i = 0, j = 0; while (i < left_size|| j < right_size) { if (i == left_size) { a[i+j] = right_a[j]; b[i+j] = right_b[j]; j++; } else if (j == right_size) { a[i+j] = left_a[i]; b[i+j] = left_b[i]; i++; } else if (left_a[i] <= right_a[j]) { a[i+j] = left_a[i]; b[i+j] = left_b[i]; i++; } else { a[i+j] = right_a[j]; b[i+j] = right_b[j]; j++; } } return; } void merge(int*a,int*left,int*right,int left_size, int right_size){ int i = 0, j = 0; while (i < left_size|| j < right_size) { if (i == left_size) { a[i+j] = right[j]; j++; } else if (j == right_size) { a[i+j] = left[i]; i++; } else if (str[left[i]] <= str[right[j]]) { a[i+j] = left[i]; i++; } else { a[i+j] = right[j]; j++; } } return; } void sort_a(int*a,int size){ if (size < 2) return; int m = (size+1)/2,i; int *left,*right; left=(int*)malloc(m*sizeof(int)); right=(int*)malloc((size-m)*sizeof(int)); for(i=0;i<m;i++) left[i]=a[i]; for(i=0;i<size-m;i++) right[i]=a[i+m]; sort_a(left,m); sort_a(right,size-m); merge(a,left,right,m,size-m); free(left); free(right); return; } void suffixSort(int n){ //sort suffixes according to their first characters int h,i,j,k; for (i=0; i<n; ++i){ pos[i] = i; } sort_a(pos, n); //{pos contains the list of suffixes sorted by their first character} for (i=0; i<n; ++i){ bh[i] = i == 0 || str[pos[i]] != str[pos[i-1]]; b2h[i] = 0; } for (h = 1; h < n; h <<= 1){ //{bh[i] == false if the first h characters of pos[i-1] == the first h characters of pos[i]} int buckets = 0; for (i=0; i < n; i = j){ j = i + 1; while (j < n && !bh[j]) j++; next[i] = j; buckets++; } if (buckets == n) break; // We are done! Lucky bastards! //{suffixes are separted in buckets containing strings starting with the same h characters} for (i = 0; i < n; i = next[i]){ cnt[i] = 0; for (j = i; j < next[i]; ++j){ rank[pos[j]] = i; } } cnt[rank[n - h]]++; b2h[rank[n - h]] = 1; for (i = 0; i < n; i = next[i]){ for (j = i; j < next[i]; ++j){ int s = pos[j] - h; if (s >= 0){ int head = rank[s]; rank[s] = head + cnt[head]++; b2h[rank[s]] = 1; } } for (j = i; j < next[i]; ++j){ int s = pos[j] - h; if (s >= 0 && b2h[rank[s]]){ for (k = rank[s]+1; !bh[k] && b2h[k]; k++) b2h[k] = 0; } } } for (i=0; i<n; ++i){ pos[rank[i]] = i; bh[i] |= b2h[i]; } } for (i=0; i<n; ++i){ rank[pos[i]] = i; } } // End of suffix array algorithm void LCP(int n){ int l=0,i,j,k; for(i=0;i<n;i++){ k=rank[i]; if(!k) continue; j=pos[k-1]; while(str[i+l]==str[j+l]) l++; lcp[k]=l; if(l>0) l--; } lcp[0]=0; return; } String Function Calculation C++ Solution #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; } String Function Calculation C Sharp Solution using System.CodeDom.Compiler; using System.Collections.Generic; using System.Collections; using System.ComponentModel; using System.Diagnostics.CodeAnalysis; using System.Globalization; using System.IO; using System.Linq; using System.Reflection; using System.Runtime.Serialization; using System.Text.RegularExpressions; using System.Text; using System; class Result { public static int[] CreateSuffixArray(string t) { int strLength = t.Length; int[] rank = new int[strLength + 1]; int[] sa = new int[strLength]; int[] tmpRank = new int[strLength + 1]; // Initialize Suffix Array sa for (int i = 0; i < strLength; i++) sa[i] = i; // Initialize rank[] for 0-th iteration // Define rank '0' is 'a' // Initial value is a rank value of 1st character of each suffix. for (int i = 0; i < strLength; i++) rank[i] = t[sa[i]] - 'a'; // Iterate untill compare length reaches t.length. // - stp = Number of iteration (e.g.) stp=n means n-th iteration. // - cmpCnt = Substring length of current iteration. //int stp = 1, cmpCnt = 1; for (int stp = 1, cmpCnt = 1; cmpCnt < strLength; stp++, cmpCnt *= 2) { // Sort sa[] Array.Sort(sa, (a, b) => { if (rank[a] != rank[b]) { return rank[a] - rank[b]; } return ((a + cmpCnt < strLength) ? rank[a + cmpCnt] : -1) - ((b + cmpCnt < strLength) ? rank[b + cmpCnt] : -1); }); // Update rank[] for next iteration // - Initialize rank of first suffix to '0' tmpRank[sa[0]] = 0; int currentRank = 0; for (int i = 1; i < strLength; i++) { int r00 = rank[sa[i - 1]]; int r01 = rank[sa[i]]; int r10 = (sa[i - 1] + cmpCnt < strLength) ? rank[sa[i - 1] + cmpCnt] : -1; int r11 = (sa[i] + cmpCnt < strLength) ? rank[sa[i] + cmpCnt] : -1; if (r00 != r01 || r10 != r11) { currentRank++; } tmpRank[sa[i]] = currentRank; } for (int i = 0; i < strLength; i++) { rank[i] = tmpRank[i]; } } return sa; } public static int[] GetLcp2(string t, int[] sa) { int[] lcpArry = new int[sa.Length]; int[] rank = new int[sa.Length]; int len = sa.Length; for (int i = 0; i < len; i++) rank[sa[i]] = i; int localLcp = 0; for (int i = 0; i < len; i++) { if (rank[i] == len - 1) { localLcp = 0; continue; } int j = sa[rank[i] + 1]; while (i + localLcp < len && j + localLcp < len && t[i + localLcp] == t[j + localLcp]) localLcp++; lcpArry[rank[i]] = localLcp; if (localLcp != 0) localLcp--; } return lcpArry; } public static int FindMax3(int[] lcpArry) { int saLen = lcpArry.Length; int maxVal = 0; Stack<int> stack = new Stack<int>(); int idx = 0; //int thresLength = 0; int substLength = 0; int occurunce = 0; while (idx < saLen) { if (stack.Count == 0 || lcpArry[idx] >= lcpArry[stack.Peek()]) { stack.Push(idx++); continue; } substLength = lcpArry[stack.Pop()]; occurunce = (stack.Count != 0) ? (idx - stack.Peek()) : (idx + 1); int tmp = substLength * occurunce; if (tmp > maxVal) maxVal = tmp; } while (stack.Count != 0) { substLength = lcpArry[stack.Pop()]; occurunce = (stack.Count != 0) ? (idx - stack.Peek()) : (idx + 1); int tmp = substLength * occurunce; if (tmp > maxVal) maxVal = tmp; } return (maxVal < saLen) ? saLen : maxVal; } public static int maxValue(string t) { // Get suffix array as 'sa' var sa = CreateSuffixArray(t); var lcpArry = GetLcp2(t, sa); var maxValue = FindMax3(lcpArry); return maxValue; } } class Solution { public static void Main(string[] args) { TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true); string t = Console.ReadLine(); int result = Result.maxValue(t); textWriter.WriteLine(result); textWriter.Flush(); textWriter.Close(); } } String Function Calculation Java Solution 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(); } } String Function Calculation JavaScript Solution 'use strict'; const fs = require('fs'); process.stdin.resume(); process.stdin.setEncoding('utf-8'); let inputString = ''; let currentLine = 0; process.stdin.on('data', function(inputStdin) { inputString += inputStdin; }); process.stdin.on('end', function() { inputString = inputString.split('\n'); main(); }); function readLine() { return inputString[currentLine++]; } /* * Complete the 'maxValue' function below. * * The function is expected to return an INTEGER. * The function accepts STRING t as parameter. */ function buildSuffixArray (txt) { const len = txt.length const suffixes = new Array(len) const aCode = 'a'.charCodeAt(0) // sort based on first 2 characters for (let i = 0; i !== len; i++) { const nextIndex = i + 1 suffixes[i] = { index: i, rank: [ txt.charCodeAt(i) - aCode, nextIndex < len ? txt.charCodeAt(nextIndex) - aCode : -1 ] } } suffixes.sort(compare) // console.log(JSON.stringify(suffixes)) // sort based on first 4 characters and so on const ind = new Array(len) // get the index in suffixes[] from origin index for (let k = 4; k < 2 * len; k*=2) { // assign rank to suffixes[0] let rank = 0 let prevRank = suffixes[0].rank[0] suffixes[0].rank[0] = rank ind[suffixes[0].index] = 0 // assign rank from suffixes[1] to suffixes[len -1] for (let i = 1; i < len; i++) { if (suffixes[i].rank[0] === prevRank && suffixes[i].rank[1] === suffixes[i - 1].rank[1]) { prevRank = suffixes[i].rank[0] suffixes[i].rank[0] = rank } else { prevRank = suffixes[i].rank[0] suffixes[i].rank[0] = ++rank } ind[suffixes[i].index] = i } // assign next rank from suffixes[0] to suffixes[len -1] for (let i = 0; i < len; i++) { let nextIndex = suffixes[i].index + Math.floor(k / 2) // origin index suffixes[i].rank[1] = nextIndex < len ? suffixes[ind[nextIndex]].rank[0]: -1 } // sort the suffixes according to first k characters suffixes.sort(compare) } // console.log(JSON.stringify(suffixes)) // build suffix array const suffixArray = suffixes.map(suffix => suffix.index) // for (let i = 0; i < len; i++) { // suffixArray[i] = suffixes[i].index // } return suffixArray } function compare (a, b) { if (a.rank[0] === b.rank[0]) { if (a.rank[1] < b.rank[1]) { return -1 } else if (a.rank[1] > b.rank[1]) { return 1 } else { return 0 } } else if (a.rank[0] < b.rank[0]) { return -1 } else { return 1 } } // kasai algorithm for building lcp array function buildLcpKasai (suffixArr, txt) { const len = suffixArr.length const lcp = new Array(len) // An auxiliary array to store inverse of suffix array // elements. For example if suffixArr[0] is 5, the // invSuff[5] would store 0. // In fact invSuff[i], i present index in original text, // also present the suffix string, // and invSuff[i] present index in suffixArr. // You can take invSuff as a map between origin text index(suffix string) and suffixArr index. const invSuff = new Array(len) // init for (let i = 0; i !== len; i++) { lcp[i] = 0 invSuff[suffixArr[i]] = i } // build lcp let nextLcp = 0 for (let i = 0; i !== len; i++) { // i is the index of origin text, so in fact we process // all suffix in origin text one by one // remember invSuff[i] is index in suffixArr. // lcp[len - 1] is zero if (invSuff[i] === len - 1) { nextLcp = 0 continue } const nextSuffixIndex = suffixArr[invSuff[i] + 1] // index in origin text while (i + nextLcp < len && nextSuffixIndex + nextLcp < len && txt[i + nextLcp] === txt[nextSuffixIndex + nextLcp]) { nextLcp++ } lcp[invSuff[i]] = nextLcp // because lcp of next suffix in text will be at least ${nextLcp - 1} nextLcp > 0 && (nextLcp--) } // return lcp return lcp } function stringFuctionCalculation (txt) { const suffixArr = buildSuffixArray(txt) const lcp = buildLcpKasai(suffixArr, txt) const len = txt.length let result = len for (let i = 0; i < len; i++) { // because it's common prefix, means at least there are two of the common prefix let count = 2 for (let j = i - 1; j >= 0; j--) { if (lcp[j] >= lcp[i]) { count++ } else { break } } for (let j = i + 1; j < len; j++) { if (lcp[j] >= lcp[i]) { count++ } else { break } } result = Math.max(result, count * lcp[i]) } return result } function main() { const ws = fs.createWriteStream(process.env.OUTPUT_PATH); const t = readLine(); const result = stringFuctionCalculation(t); ws.write(result + '\n'); ws.end(); } String Function Calculation Python Solution #!/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): """ l: iterable of keys returns: a list with integer keys """ 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): """ suffix matrix of s O(n * log(n)^2) """ 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): """ longest common prefix O(log(n)) sm: suffix matrix """ 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): # print() # print(a) # print() 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() Other Solutions HackerRank Build a Palindrome Problem Solution HackerRank Build a String Problem Solution c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython