String Function Calculation

                            Solution in C :

In   C++  :








#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <cmath>
#include <memory.h>
using namespace std;
typedef long long ll;

const int N = 3e5+6;

#define link ololink
int link[N], len[N], to[N][26], cnt[N],  d;
vector<int> v[N];
char s[N];

int main(){
    //freopen("input.txt","r",stdin);// freopen("output.txt","w",stdout);
    
    int n, m;
    
    gets(s);
    
    n = strlen(s);
    
    d = 0;
    int l = d++;
    
    link[l] = -1;
    for(int i=0;i<n;++i){
    	int c = s[i]-'a';
    	int x = d++;
    	len[x] = len[l]+1;
    	cnt[x] = 1;
    	for(;l!=-1 && !to[l][c]; l=link[l]) to[l][c]=x;
    	if(~l){
    		int p = to[l][c];
    		if(len[p]==len[l]+1) link[x] = p; else{
    			int q = d++;
    			memcpy(to[q], to[p], sizeof(to[p]));
    			link[q] = link[p];
    			len[q] = len[l]+1;
    			for(;l!=-1 && to[l][c]==p; l=link[l]) to[l][c] = q;
    			link[x] = link[p] = q;
    		}
    	}
    	l = x;
    }
    
    ll ans = 0;
    for(int i=0;i<d;++i) v[len[i]].push_back(i);
    
    for(l=n;l;--l)
    for(int k=0;k<v[l].size();++k){
    	int i = v[l][k];
    	int j = link[i];
    	ans = max(ans, 1LL*len[i]*cnt[i]);
    	cnt[j]+=cnt[i];
    }
    
    cout<<ans<<endl;
    
    return 0;
}









In  Java  :








import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Solution {

    static class SuffixAutomata {

        static class Vertex {
            Vertex suffixLink = null;
            Vertex[] edges;
            int log = 0;

            int terminals;
            boolean visited;

            public Vertex(Vertex o, int log) {
                edges = o.edges.clone();
                this.log = log;
            }

            public Vertex(int log) {
                edges = new Vertex[26];
                this.log = log;
            }

            long dp() {
                if (visited) {
                    return 0;
                }
                visited = true;
                long r = 0;
                for (Vertex v : edges) {
                    if (v != null) {
                        r = Math.max(r, v.dp());
                        terminals += v.terminals;
                    }
                }
                return Math.max(r, 1L * log * terminals);
            }
        }

        Vertex root, last;

        public SuffixAutomata(String str) {
            last = root = new Vertex(0);
            for (int i = 0; i < str.length(); i++) {
                addChar(str.charAt(i));
            }
            addTerm();
        }

        private void addChar(char c) {
            Vertex cur = last;
            last = new Vertex(cur.log + 1);
            while (cur != null && cur.edges[c - 'a'] == null) {
                cur.edges[c - 'a'] = last;
                cur = cur.suffixLink;
            }
            if (cur != null) {
                Vertex q = cur.edges[c - 'a'];
                if (q.log == cur.log + 1) {
                    last.suffixLink = q;
                } else {
                    Vertex r = new Vertex(q, cur.log + 1);
                    r.suffixLink = q.suffixLink;
                    q.suffixLink = r;
                    last.suffixLink = r;
                    while (cur != null) {
                        if (cur.edges[c - 'a'] == q) {
                            cur.edges[c - 'a'] = r;
                        } else {
                            break;
                        }
                        cur = cur.suffixLink;
                    }
                }
            } else {
                last.suffixLink = root;
            }
        }

        private void addTerm() {
            Vertex cur = last;
            while (cur != null) {
                cur.terminals++;
                cur = cur.suffixLink;
            }
        }
    }

    public static void solve(Input in, PrintWriter out) throws IOException {
        String s = in.next();
        SuffixAutomata a = new SuffixAutomata(s);
        out.println(a.root.dp());
    }

    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        solve(new Input(new BufferedReader(new InputStreamReader(System.in))), out);
        out.close();
    }

    static class Input {
        BufferedReader in;
        StringBuilder sb = new StringBuilder();

        public Input(BufferedReader in) {
            this.in = in;
        }

        public Input(String s) {
            this.in = new BufferedReader(new StringReader(s));
        }

        public String next() throws IOException {
            sb.setLength(0);
            while (true) {
                int c = in.read();
                if (c == -1) {
                    return null;
                }
                if (" \n\r\t".indexOf(c) == -1) {
                    sb.append((char)c);
                    break;
                }
            }
            while (true) {
                int c = in.read();
                if (c == -1 || " \n\r\t".indexOf(c) != -1) {
                    break;
                }
                sb.append((char)c);
            }
            return sb.toString();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
    }
}










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;
}










In   Python3 :








#!/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()