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 t
Jane wants to know the maximum value of f(s) among all the substrings ($) of string t.
Can you help her?
Input Format
A single line containing string t.
Output Format
Print 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.
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
