HackerRank String Function Calculation Solution

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

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

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()