HackerRank String Function Calculation Solution

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

//void test(int n) {
//	int i;
//	
//	printf("suffix array:\n");
//	for (i = 0; i < n; ++ i) printf("%s\n", str + sa[i]);
//	
//	printf("rank array:\n");
//	for (i = 0; i < n; ++ i) printf("%s, %d\n", str+i, rank[i]);
//	
//	printf("height array:\n");
//	for (i = 0; i < n; ++ i) printf("%d\n", height[i]);
//}

int main() {
//	freopen("input.txt", "r", stdin);
	
    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);
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    return 0;
}

#include <cstdio>   
#include <cstdlib>   
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

const int N = 201000;   
int wa[N], wb[N], ws[N*2], wv[N];   
int Rank[N], sa[N], height[N], r[N];   
char s[N];
   
int cmp( int* r, int a, int b, int L ){   
    return r[a]== r[b] && r[a+ L]== r[b+ L];   
}

long long mul(long long x,long long y) {
	return x * y;
}   
   
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 ) ws[i]= 0;   
    for( i= 0; i< n; ++i ) ws[ x[i]= r[i] ]++;   
    for( i= 1; i< m; ++i ) ws[i]+= ws[i-1];   
    for( i= n- 1; i>= 0; i-- ) sa[ --ws[ 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 ) ws[i]= 0;   
        for( i= 0; i< n; ++i ) ws[ wv[i] ]++;   
        for( i= 1; i< m; ++i ) ws[i]+= ws[i-1];   
        for( i= n- 1; i>= 0; i-- ) sa[ --ws[ wv[i] ] ]= y[i];   
   
        t= x, x= y, y= t, p= 1; x[ sa[0] ]= 0;   
        for( i= 1; i< n; ++i )   
            x[ sa[i] ]= cmp( y, sa[i-1], sa[i], j )? p- 1: p++;   
    }   
}


long long largestRectangleArea(vector<int> &height) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        int n = height.size();
	long long result = 0;
        stack<int> s;
        for (int i = 0; i < n; ++i) {
	   //printf("%d\n",height[i]);
            while ((!s.empty()) && (height[s.top()] > height[i])) {
                int h = height[s.top()];
                s.pop();
                result = max(result, mul((i  - (s.empty()?(-1):s.top())) , h));
                
            }
            s.push(i);
        }
        while (!s.empty()) {
            int h = height[s.top()];
            s.pop();
	    //printf("h = %d\n",h);
            result = max(result, mul((n  - (s.empty()?(-1):s.top())) , h));
        }
        return result;
        
    }   
   
void callheight( int* r, int*sa, int n ){   
    int i, j, k= 0;   
    for( i= 1; i<= n; ++i ) Rank[ sa[i] ]= i;   
   
    for( i= 0; i< n; height[ Rank[i++] ]= k )   
        for( k?k--:0, j= sa[ Rank[i]- 1]; r[i+k]== r[j+k]; k++ );   
   
}   
   
   
int main(){   
    scanf("%s",s );
    int n = strlen(s); 
    for(int i= 0; i < n; ++i ){   
        r[i] = s[i] - 'a' + 1; 
    }   
    r[n]= 0;   
    da( r, sa, n + 1, 27);   
    callheight( r, sa, n );  
    vector<int> a; 
    for (int i = 0; i <= n; ++i) {
	//printf("%d\n",height[i]);
	a.push_back(height[i]);
    }
    printf("%lld\n", max((long long) n, largestRectangleArea(a)));
    return 0;
}
	

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

#!/usr/bin/python

def suffix_array(line):
    isa, sa, lb = [0] * len(line), [0] * len(line), [0] * len(line)
    for i in xrange(len(line)): sa[i] = ord(line[i])

    size = 1
    while size <= len(line):
        for i in xrange(len(lb)):
            if i + size < len(line): lb[i] = ((sa[i], sa[i + size]), i)
            else: lb[i] = ((sa[i], -1), i)
        lb.sort()
        sa[lb[0][1]] = 0
        for i in xrange(1, len(lb)):
            cls, idx = lb[i]
            if cls == lb[i - 1][0]: sa[idx] = sa[lb[i - 1][1]]
            else: sa[idx] = sa[lb[i - 1][1]] + 1
        size *= 2

    for i, p in enumerate(sa): isa[p] = i
    return isa, sa

def lcp(line, sa, rank):
    lcp = [0] * len(sa)
    h = 0
    for i in xrange(len(line)):
        if rank[i] == 0:
            continue
        j = sa[rank[i] - 1]
        while line[i + h] == line[j + h]: h += 1
        lcp[rank[i]] = h
        if h > 0: h -= 1
    return lcp

def solve1(line):
    line = line + chr(0)
    sa, rank = suffix_array(line)
    lp = lcp(line, sa, rank)
    lp.append(0)

    ans, st = len(line) - 1, []
    suffix, length, count = 0, len(line) - 1, 1
    for i, l in enumerate(lp):
        pos = i
        while st and st[-1][1] > l:
            j, h = st.pop()
            pos = j
            if (i - j + 1) * h > ans:
                ans = (i - j + 1) * h
                suffix, length, count = sa[j - 1], h, i - j + 1
        if not st or st[-1][1] < l:
            st.append((pos, l))

    #print sa
    #print lp

    #print 'Sub[{}:{}] count={}'.format(suffix, suffix + length, count)
    #print line[suffix:suffix + length]
    return ans

def solve2(line):
    class Substr:
         def __init__(self, line, i, j):
             self.line = line
             self.b = i
             self.e = j
             self._hash = hash(line[i:j])
         def __hash__(self):
             return self._hash
         def __eq__(self, other):
             if hash(self) != hash(other):
                 return False
             return self.line[self.b:self.e] == other.line[other.b:other.e]
         def __ne__(self, other):
             if hash(self) != hash(other):
                 return True
             return self.line[self.b:self.e] != other.line[other.b:other.e]
         def __len__(self):
             return self.e - self.b
    subs = {}
    ans = len(line)
    suffix, length, count = 0, len(line), 1
    for i in xrange(len(line)):
        for j in xrange(i + 1, len(line) + 1):
            sub = Substr(line, i, j)
            occ = subs.get(sub, 0) + 1
            subs[sub] = occ
            if occ * len(sub) > ans:
                ans = occ * len(sub)
                suffix, length, count = i, j - i, occ
    print 'Sub[{}:{}] count={}'.format(suffix, suffix + length, count)
    print line[suffix:suffix + length]
    return ans

def main():
    line = raw_input()
    print solve1(line)
    #assert solve1(line) == solve2(line)

main()

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.replace(/\s*$/, '')
        .split('\n')
        .map(str => str.replace(/\s*$/, ''));

    main();
});

function readLine() {
    return inputString[currentLine++];
}

// Complete the maxValue function below.
// nlogn algorithm for building suffix array
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();

    let result = stringFuctionCalculation(t);

    ws.write(result + "\n");

    ws.end();
}

object Solution {
    import io.StdIn._
    import collection.mutable.Stack

    def visitLen(a:Array[Int]) = {
        var h = Stack[(Int, Int)]((-1, -1))
        Array.tabulate(a.size){i => {
            while (h.top._2 >= a(i)) h.pop
            val r = i - h.top._1
            h.push(i -> a(i)); r
        }}
    }

    def main(args:Array[String]) {
        val sa = new SuffixArray(readLine.view.map{_.toLong}.toArray)
        val a = Array.tabulate(sa.sa.size - 1) {
            i => sa.lcp(sa.sa(i), sa.sa(i + 1))
        }
        var m = a.size
        val aL = visitLen(a)
        val aR = visitLen(a.reverse).reverse
        for (i <- 0 until a.size) {
            val k = (aL(i) + aR(i)) * a(i)
            if (k > m) m = k
        }
        println(m)
    }

    class SuffixArray(a:Array[Long]) {
        val n = a.size
        val m = Math.getExponent(n) + 1
        val b = Array.fill(m, n + 1){0L}
        b(0) = a :+ 0L

        def cityHash(x1:Long, x2:Long) = {
            val kMul = 0x9ddfea08eb382d69L
            var a = x1 * kMul
            a ^= a >>> 47
            var b = (a ^ x2) * kMul
            b ^ (b >>> 47)
        }

        for (i <- 1 until m; j <- 0 until n) b(i)(j) = {
            val j0 = j + (1 << i - 1)
            cityHash(b(i - 1)(j), if (j0 <= n) b(i - 1)(j0) else 0L)
        }

        def lcp(n1:Int, n2:Int) = {
            var k = 0
            for (i <- Range(m - 1, -1, -1)) {
                if (b(i)(n1 + k) == b(i)(n2 + k)) k += 1 << i
            }; k
        }

        def less(n1:Int, n2:Int):Boolean = {
            if (b(0)(n1) < b(0)(n2)) return true
            if (b(0)(n1) > b(0)(n2)) return false
            val k = lcp(n1, n2)
            b(0)(n1 + k) < b(0)(n2 + k)
        }

        lazy val sa = Array.range(0, n + 1).sortWith{less}
    }
}

program j01;
const maxn=100086;
var t:array[0..5*maxn]of record son:array['a'..'z']of longint;dis,fa:longint; end;
	s:ansistring;
	len,cnt,root,last:longint;
	ans:int64;
	id,sum:array[0..5*maxn]of longint;
	num:array[0..5*maxn]of int64;

function max(a,b:int64):int64;inline;begin if a>b then exit(a) else exit(b); end;
function newnode(d:longint):longint;inline;begin inc(cnt);t[cnt].dis:=d;exit(cnt); end;

procedure ins(ch:char);
var p,np,q,nq:longint;
begin
	p:=last;np:=newnode(t[p].dis+1);last:=np;
	num[np]:=1;
	while(p>0)and(t[p].son[ch]=0)do
	begin
		t[p].son[ch]:=np;p:=t[p].fa;
	end;
	if p=0 then t[np].fa:=root else
	begin
		q:=t[p].son[ch];
		if t[q].dis=t[p].dis+1 then t[np].fa:=q else
		begin
			nq:=newnode(t[p].dis+1);
			t[nq].son:=t[q].son;
			t[nq].fa:=t[q].fa;t[q].fa:=nq;t[np].fa:=nq;
			while t[p].son[ch]=q do
			begin
				t[p].son[ch]:=nq;p:=t[p].fa;
			end;
		end;
	end;
end;
	
procedure build;
var i:longint;
begin
	root:=1;cnt:=1;last:=1;len:=length(s);
	for i:=1 to len do ins(s[i]);
	fillchar(sum,sizeof(sum),0);
	for i:=1 to cnt do inc(sum[t[i].dis]);
	for i:=1 to len do inc(sum[i],sum[i-1]);
	for i:=cnt downto 1 do
	begin
		id[sum[t[i].dis]]:=i;dec(sum[t[i].dis]);
	end;
end;

procedure solve;
var i,p:longint;
begin
	ans:=0;
	for i:=cnt downto 1 do
	begin
		p:=id[i];ans:=max(ans,num[p]*t[p].dis);
		//writeln(num[p],' ',t[p].dis);
		inc(num[t[p].fa],num[p]);
	end;
end;
	
begin
	readln(s);
	build;
	solve;
	writeln(ans);
end.