Problem:


Score : 100 points

Problem Statement

You are given a string of length N. Calculate the number of distinct substrings of S.

Constraints

1 \leq N \leq 500,000

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S

Output

Print the answer.

Sample Input 1

abcbcba

Sample Output 1

21

Sample Input 2

mississippi

Sample Output 2

53

Sample Input 3

ababacaca

Sample Output 3

33

Sample Input 4

aaaaa

Sample Output 4

5



Sample input:
abcbcba


Sample output:
21

Submission status: Accepted

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include,/opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False
from libcpp cimport bool
from libcpp.string cimport string
from libcpp.vector cimport vector

cdef extern from "/opt/atcoder-stl/atcoder/dsu.hpp" namespace "atcoder":
    cpdef cppclass dsu:
        dsu(int n)
        int merge(int a, int b)
        bool same(int a, int b)
        int leader(int a)
        int size(int a)
        vector[vector[int]] groups()
cdef class dsu_:
    cdef dsu *ptr
    def __cinit__(self, int n): self.ptr = new dsu(n)
    def __dealloc__(self): del self.ptr
    cpdef int merge(self,a,b): return self.ptr.merge(a,b)
    cpdef bool same(self,a,b): return self.ptr.same(a,b)
    cpdef int leader(self,a): return self.ptr.leader(a)
    cpdef int size(self,a): return self.ptr.size(a)
    cpdef vector[vector[int]] groups(self): return self.ptr.groups()

cdef extern from "/opt/atcoder-stl/atcoder/fenwicktree.hpp" namespace "atcoder":
    cdef cppclass fenwick_tree[T]:
        fenwick_tree()
        fenwick_tree(int n)
        void add(int p, T x)
        T sum(int l, int r)
cdef class fenwick_tree_:
    cdef fenwick_tree[int] *ptr
    def __cinit__(self, int n): self.ptr = new fenwick_tree[int](n)  
    def __dealloc__(self): del self.ptr
    cpdef void add(self, int p, long x): self.ptr.add(p, x)
    cpdef long sum(self, int l, int r): return self.ptr.sum(l, r)

cdef extern from "/opt/atcoder-stl/atcoder/string.hpp" namespace "atcoder":
    vector[int] suffix_array(vector[int] s, int upper)
    vector[int] suffix_array(vector[long] s)
    vector[int] suffix_array(string s)
    vector[int] lcp_array(vector[long] s, vector[int] sa)
    vector[int] lcp_array(string s, vector[int] sa)
    vector[int] z_algorithm(vector[long] s)
    vector[int] z_algorithm(string s)
cpdef vector[int] suffix_array_u(vector[int] s, int upper): return suffix_array(s, upper)
cpdef vector[int] suffix_array_l(vector[long] s): return suffix_array(s)
cpdef vector[int] suffix_array_s(string s): return suffix_array(s)
cpdef vector[int] lcp_array_l(vector[long] s, vector[int] sa): return lcp_array(s, sa)
cpdef vector[int] lcp_array_s(string s, vector[int] sa): return lcp_array(s, sa)
cpdef vector[int] z_algorithm_l(vector[long] s): return z_algorithm(s)
cpdef vector[int] z_algorithm_s(string s): return z_algorithm(s)
"""

import os
try:
    from atcoder import *
except:
    open('atcoder.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')

s=list(map(ord,input()))
n=len(s)
sa=suffix_array_l(s)
print(n*(n+1)//2-sum(lcp_array_l(s,sa)))

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np


def solve(inp):
    def induce(s, n, sa, ls, sum_s, sum_l, lms):
        sa.fill(-1)
        buf = np.zeros_like(sum_s)

        buf[:] = sum_s
        for i in range(lms.size):
            d = lms[i]
            if d == n:
                continue
            sa[buf[s[d]]] = d
            buf[s[d]] += 1

        buf[:] = sum_l
        sa[buf[s[n - 1]]] = n - 1
        buf[s[n - 1]] += 1
        for i in range(n):
            v = sa[i]
            if v >= 1 and ls[v - 1] == 0:
                sa[buf[s[v - 1]]] = v - 1
                buf[s[v - 1]] += 1

        buf[:] = sum_l
        for i in range(n - 1, -1, -1):
            v = sa[i]
            if v >= 1 and ls[v - 1] == 1:
                buf[s[v - 1] + 1] -= 1
                sa[buf[s[v - 1] + 1]] = v - 1

    def suffix_array(s, upper):

        stack = []

        while True:
            n = s.size
            sa = np.zeros(n, np.int64)
            if n < 2:
                break
            if n == 2:
                sa[int(s[0] < s[1])] = 1
                break

            ls = np.zeros(n, np.int64)
            for i in range(n - 2, -1, -1):
                ls[i] = ls[i + 1] if s[i] == s[i + 1] else s[i] < s[i + 1]
            sum_l = np.zeros(upper + 1, np.int64)
            sum_s = np.zeros(upper + 1, np.int64)
            for i in range(n):
                if ls[i]:
                    sum_l[s[i] + 1] += 1
                else:
                    sum_s[s[i]] += 1

            for i in range(upper + 1):
                sum_s[i] += sum_l[i]
                if i < upper:
                    sum_l[i + 1] += sum_s[i]

            lms_map = np.full(n + 1, -1, np.int64)
            m = 0
            for i in range(1, n):
                if ls[i - 1] == 0 and ls[i] == 1:
                    lms_map[i] = m
                    m += 1

            lms = np.zeros(m, np.int64)
            idx = 0
            for i in range(1, n):
                if ls[i - 1] == 0 and ls[i] == 1:
                    lms[idx] = i
                    idx += 1

            induce(s, n, sa, ls, sum_s, sum_l, lms)

            if m == 0:
                break

            sorted_lms = np.zeros(m, np.int64)
            idx = 0
            for i in range(n):
                if lms_map[sa[i]] != -1:
                    sorted_lms[idx] = sa[i]
                    idx += 1
            rec_s = np.zeros(m, np.int64)
            rec_upper = 0
            rec_s[lms_map[sorted_lms[0]]] = 0
            for i in range(1, m):
                l = sorted_lms[i - 1]
                r = sorted_lms[i]
                end_l = lms[lms_map[l] + 1] if lms_map[l] + 1 < m else n
                end_r = lms[lms_map[r] + 1] if lms_map[r] + 1 < m else n
                same = True
                if end_l - l != end_r - r:
                    same = False
                else:
                    while l < end_l:
                        if s[l] != s[r]:
                            break
                        l += 1
                        r += 1
                    if l == n or s[l] != s[r]:
                        same = False
                if not same:
                    rec_upper += 1
                rec_s[lms_map[sorted_lms[i]]] = rec_upper

            stack.append((s, sa, ls, sum_s, sum_l, lms, sorted_lms))

            s = rec_s
            upper = rec_upper

        while stack:
            s, _sa, ls, sum_s, sum_l, lms, sorted_lms = stack.pop()
            n = s.size
            m = lms.size
            for i in range(m):
                sorted_lms[i] = lms[sa[i]]
            induce(s, n, _sa, ls, sum_s, sum_l, sorted_lms)
            sa = _sa

        return sa

    def lcp_array(s, sa):
        n = s.size
        rnk = np.argsort(sa)
        lcp = np.zeros(n - 1, np.int64)
        h = 0
        for i in range(n):
            if h > 0:
                h -= 1
            if rnk[i] == 0:
                continue
            j = sa[rnk[i] - 1]
            while j + h < n and i + h < n:
                if s[j + h] != s[i + h]:
                    break
                h += 1
            lcp[rnk[i] - 1] = h
        return lcp

    sa = suffix_array(inp, 25)
    lcp = lcp_array(inp, sa)

    n = inp.size
    return n * (n + 1) // 2 - lcp.sum()


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromiter((ord(c) - 97 for c in input()), np.int64)
ans = solve(inp)
print(ans)

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np


def solve(inp):
    def induce(s, n, sa, ls, sum_s, sum_l, lms):
        sa.fill(-1)

        buf = sum_s.copy()
        for i in range(lms.size):
            d = lms[i]
            if d == n:
                continue
            sa[buf[s[d]]] = d
            buf[s[d]] += 1

        buf = sum_l.copy()
        sa[buf[s[n - 1]]] = n - 1
        buf[s[n - 1]] += 1
        for i in range(n):
            v = sa[i]
            if v >= 1 and ls[v - 1] == 0:
                sa[buf[s[v - 1]]] = v - 1
                buf[s[v - 1]] += 1

        buf = sum_l.copy()
        for i in range(n - 1, -1, -1):
            v = sa[i]
            if v >= 1 and ls[v - 1] == 1:
                buf[s[v - 1] + 1] -= 1
                sa[buf[s[v - 1] + 1]] = v - 1

    def suffix_array(s, upper):

        stack = []

        while True:
            n = s.size
            sa = np.zeros(n, np.int64)
            if n < 2:
                break
            if n == 2:
                sa[int(s[0] < s[1])] = 1
                break

            ls = np.zeros(n, np.int64)
            for i in range(n - 2, -1, -1):
                ls[i] = ls[i + 1] if s[i] == s[i + 1] else s[i] < s[i + 1]
            sum_l = np.zeros(upper + 1, np.int64)
            sum_s = np.zeros(upper + 1, np.int64)
            for i in range(n):
                if ls[i]:
                    sum_l[s[i] + 1] += 1
                else:
                    sum_s[s[i]] += 1

            for i in range(upper + 1):
                sum_s[i] += sum_l[i]
                if i < upper:
                    sum_l[i + 1] += sum_s[i]

            lms_map = np.full(n + 1, -1, np.int64)
            m = 0
            for i in range(1, n):
                if ls[i - 1] == 0 and ls[i] == 1:
                    lms_map[i] = m
                    m += 1

            lms = np.zeros(m, np.int64)
            idx = 0
            for i in range(1, n):
                if ls[i - 1] == 0 and ls[i] == 1:
                    lms[idx] = i
                    idx += 1

            induce(s, n, sa, ls, sum_s, sum_l, lms)

            if m == 0:
                break

            sorted_lms = np.zeros(m, np.int64)
            idx = 0
            for i in range(n):
                if lms_map[sa[i]] != -1:
                    sorted_lms[idx] = sa[i]
                    idx += 1
            rec_s = np.zeros(m, np.int64)
            rec_upper = 0
            rec_s[lms_map[sorted_lms[0]]] = 0
            for i in range(1, m):
                l = sorted_lms[i - 1]
                r = sorted_lms[i]
                end_l = lms[lms_map[l] + 1] if lms_map[l] + 1 < m else n
                end_r = lms[lms_map[r] + 1] if lms_map[r] + 1 < m else n
                same = True
                if end_l - l != end_r - r:
                    same = False
                else:
                    while l < end_l:
                        if s[l] != s[r]:
                            break
                        l += 1
                        r += 1
                    if l == n or s[l] != s[r]:
                        same = False
                if not same:
                    rec_upper += 1
                rec_s[lms_map[sorted_lms[i]]] = rec_upper

            stack.append((s, sa, ls, sum_s, sum_l, lms, sorted_lms))

            s = rec_s
            upper = rec_upper

        while stack:
            s, _sa, ls, sum_s, sum_l, lms, sorted_lms = stack.pop()
            n = s.size
            m = lms.size
            for i in range(m):
                sorted_lms[i] = lms[sa[i]]
            induce(s, n, _sa, ls, sum_s, sum_l, sorted_lms)
            sa = _sa

        return sa

    def lcp_array(s, sa):
        n = s.size
        rnk = np.argsort(sa)
        lcp = np.zeros(n - 1, np.int64)
        h = 0
        for i in range(n):
            if h > 0:
                h -= 1
            if rnk[i] == 0:
                continue
            j = sa[rnk[i] - 1]
            while j + h < n and i + h < n:
                if s[j + h] != s[i + h]:
                    break
                h += 1
            lcp[rnk[i] - 1] = h
        return lcp

    sa = suffix_array(inp, 25)
    lcp = lcp_array(inp, sa)

    n = inp.size
    return n * (n + 1) // 2 - lcp.sum()


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromiter((ord(c) - 97 for c in input()), np.int64)
ans = solve(inp)
print(ans)

Submission status: Accepted

Solution code:
# Date [ 2020-09-09 16:51:26 ]
# Problem [ i.py ]
# Author Koki_tkg

import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

# Converted AC Library from C++ to python
def sa_native(s: list):
    from functools import cmp_to_key
    def mycmp(r, l):
        if l == r: return -1
        while l < n and r < n:
            if s[l] != s[r]: return 1 if s[l] < s[r] else -1
            l += 1
            r += 1
        return 1 if l == n else -1
    n = len(s)
    sa = [i for i in range(n)]
    sa.sort(key=cmp_to_key(mycmp))
    return sa

def sa_doubling(s: list):
    from functools import cmp_to_key
    def mycmp(y, x):
        if rnk[x] != rnk[y]: return 1 if rnk[x] < rnk[y] else -1
        rx = rnk[x + k] if x + k < n else -1
        ry = rnk[y + k] if y + k < n else -1
        return 1 if rx < ry else -1
        
    n = len(s)
    sa = [i for i in range(n)]; rnk = s; tmp = [0] * n; k = 1
    while k < n:
        sa.sort(key=cmp_to_key(mycmp))
        tmp[sa[0]] = 0
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i - 1]]
            if mycmp(sa[i], sa[i - 1]) == 1: tmp[sa[i]] += 1
        tmp, rnk = rnk, tmp
        k *= 2
    return sa

def sa_is(s: list, upper: int):
    '''
    SA-IS, linear-time suffix array construction
    Reference:
    G. Nong, S. Zhang, and W. H. Chan, Two Efficient Algorithms for Linear Time Suffix Array Construction
    '''
    THRESHOLD_NATIVE = 10
    THRESHOLD_DOUBLING = 40
    n = len(s)
    if n == 0: return []
    if n == 1: return [0]
    if n == 2:
        if s[0] < s[1]:
            return [0, 1]
        else:
            return [1, 0]
    if n < THRESHOLD_NATIVE:
        return sa_native(s)
    if n < THRESHOLD_DOUBLING:
        return sa_doubling(s)
    
    sa = [0] * n
    ls = [False] * n
    for i in range(n - 2, -1, -1):
        ls[i] = ls[i + 1] if s[i] == s[i + 1] else s[i] < s[i + 1]
    
    sum_l = [0] * (upper + 1); sum_s = [0] * (upper + 1)
    for i in range(n):
        if not ls[i]:
            sum_s[s[i]] += 1
        else:
            sum_l[s[i] + 1] += 1
    for i in range(upper + 1):
        sum_s[i] += sum_l[i]
        if i < upper: sum_l[i + 1] += sum_s[i]
        
    def induce(lms: list):
        from copy import copy # ループより速く感じる
        for i in range(n): sa[i] = -1 # [-1]*n にするとバグる
        buf = [0] * (upper + 1)
        buf = copy(sum_s)
        for d in lms:
            if d == n: continue
            sa[buf[s[d]]] = d; buf[s[d]] += 1
        
        buf = copy(sum_l)
        sa[buf[s[n - 1]]] = n - 1; buf[s[n - 1]] += 1
        for i in range(n):
            v = sa[i]
            if v >= 1 and not ls[v - 1]:
                sa[buf[s[v - 1]]] = v - 1; buf[s[v - 1]] += 1
        
        buf = copy(sum_l)
        for i in range(n - 1, -1, -1):
            v = sa[i]
            if v >= 1 and ls[v - 1]:
                buf[s[v - 1] + 1] -= 1; sa[buf[s[v - 1] + 1]] = v - 1

    lms_map = [-1] * (n + 1)
    m = 0
    for i in range(1, n):
        if not ls[i - 1] and ls[i]:
            lms_map[i] = m; m += 1
    lms = [i for i in range(1, n) if not ls[i - 1] and ls[i]]
    induce(lms)

    if m:
        sorted_lms = [v for v in sa if lms_map[v] != -1]
        rec_s = [0] * m
        rec_upper = 0
        rec_s[lms_map[sorted_lms[0]]] = 0
        for i in range(1, m):
            l = sorted_lms[i - 1]; r = sorted_lms[i]
            end_l = lms[lms_map[l] + 1] if lms_map[l] + 1 < m else n
            end_r = lms[lms_map[r] + 1] if lms_map[r] + 1 < m else n
            same = True
            if end_l - l != end_r - r:
                same = False
            else:
                while l < end_l:
                    if s[l] != s[r]: break
                    l += 1
                    r += 1
                if l == n or s[l] != s[r]: same = False
            if not same: rec_upper += 1
            rec_s[lms_map[sorted_lms[i]]] = rec_upper
        
        rec_sa = sa_is(rec_s, rec_upper)

        for i in range(m):
            sorted_lms[i] = lms[rec_sa[i]]
        induce(sorted_lms)
    return sa

def suffix_array(s: list, upper: int):
    assert 0 <= upper
    for d in s:
        assert 0 <= d and d <= upper
    sa = sa_is(s, upper)
    return sa

def suffix_array2(s: list):
    from functools import cmp_to_key
    n = len(s)
    idx = [i for i in range(n)]
    idx.sort(key=cmp_to_key(lambda l, r: s[l] < s[r]))
    s2 = [0] * n
    now = 0
    for i in range(n):
        if i and s[idx[i - 1]] != s[idx[i]]: now += 1
        s2[idx[i]] = now
    return sa_is(s2, now)

def suffix_array3(s: str):
    n = len(s)
    s2 = list(map(ord, s))
    return sa_is(s2, 255)

def lcp_array(s: list, sa: list):
    '''
    Reference:
    T. Kasai, G. Lee, H. Arimura, S. Arikawa, and K. Park,
    Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its
    Applications
    '''
    n = len(s)
    assert n >= 1
    rnk = [0] * n
    for i in range(n):
        rnk[sa[i]] = i
    lcp = [0] * (n - 1)
    h = 0
    for i in range(n):
        if h > 0: h -= 1
        if rnk[i] == 0: continue
        j = sa[rnk[i] - 1]
        while j + h < n and i + h < n:
            if s[j + h] != s[i + h]: break
            h += 1
        lcp[rnk[i] - 1] = h
    return lcp

def lcp_array2(s: str, sa: list):
    n = len(s)
    s2 = list(map(ord, s))
    return lcp_array(s2, sa)

def z_algorithm(s: list):
    '''
    Reference:
    D. Gusfield,
    Algorithms on Strings, Trees, and Sequences: Computer Science and
    Computational Biology
    '''
    n = len(s)
    if n == 0: return []
    z = [-1] * n
    z[0] = 0; j = 0
    for i in range(1, n):
        k = z[i] = 0 if j + z[j] <= i else min(j + z[j] - i, z[i - j])
        while i + k < n and s[k] == s[i + k]: k += 1
        z[i] = k
        if j + z[j] < i + z[i]: j = i
    z[0] = n
    return z

def z_algorithm2(s: str):
    n = len(s)
    s2 = list(map(ord, s))
    return z_algorithm(s2)

def Main():
    s = read_str()
    sa = suffix_array3(s)
    ans = len(s) * (len(s) + 1) // 2
    for x in lcp_array2(s, sa):
        ans -= x
    print(ans)

if __name__ == '__main__':
    Main()

Submission status: Accepted

Solution code:
#-------最強ライブラリString(Python)ver25252------
#全然わからん 翻訳しただけ

from functools import cmp_to_key
THRESHOLD_NAIVE = 10
THRESHOLD_DOUBLING = 40

# ナイーブな実装？
# O(n^2 log n かな？)
def sa_naive(s):
  def cmp(r, l):
    if l == r: return -1
    while (l < n and r < n):
      if s[l] != s[r]: return 1 if s[l] < s[r] else -1
      l += 1
      r += 1
    return 1 if l == n else -1
  n = len(s)
  sa = [i for i in range(n)]
  sa.sort(key=cmp_to_key(cmp))
  return sa

# わかんねー
# O(↑と↓の間くらい)
def sa_doubling(s):
  n = len(s)
  sa = [i for i in range(n)]
  rnk = s
  tmp = [0] * n
  k = 1
  while k < n:
    def cmp(y, x):
      if rnk[x] != rnk[y]: return 1 if rnk[x] < rnk[y] else -1
      rx = rnk[x + k] if x + k < n else -1
      ry = rnk[y + k] if y + k < n else -1
      return 1 if rx < ry else -1
    sa.sort(key=cmp_to_key(cmp))
    tmp[sa[0]] = 0
    for i in range(1, n):
      tmp[sa[i]] = tmp[sa[i - 1]] + (1 if cmp(sa[i], sa[i - 1]) == 1 else 0)
    tmp, rnk = rnk, tmp
    k *= 2
  return sa

# メインディッシュ
# O(n + upper のはず)
def sa_is(s, upper):
  n = len(s)
  if n == 0: return []
  if n == 1: return [0]
  if n == 2:
    if s[0] < s[1]: return [0, 1]
    else: return [1, 0]
  if n < THRESHOLD_NAIVE:
    return sa_naive(s)
  if n < THRESHOLD_DOUBLING:
    return sa_doubling(s)

  sa = [0] * n
  ls = [False] * n
  for i in range(n - 2, -1, -1):
    ls[i] = ls[i + 1] if s[i] == s[i + 1] else s[i] < s[i + 1]
  sum_l = [0] * (upper + 1)
  sum_s = [0] * (upper + 1)
  for i in range(n):
    if not ls[i]: sum_s[s[i]] += 1
    else: sum_l[s[i] + 1] += 1
  for i in range(upper + 1):
    sum_s[i] += sum_l[i]
    if i < upper: sum_l[i + 1] += sum_s[i]

  def induce(lms):
    for i in range(n): sa[i] = -1
    buf = [0] * (upper + 1)
    for i in range(len(sum_s)): buf[i] = sum_s[i]
    for d in lms:
      if d == n: continue
      sa[buf[s[d]]] = d
      buf[s[d]] += 1
    for i in range(len(sum_l)): buf[i] = sum_l[i]
    sa[buf[s[n - 1]]] = n - 1
    buf[s[n - 1]] += 1
    for i in range(n):
      v = sa[i]
      if v >= 1 and not ls[v - 1]:
        sa[buf[s[v - 1]]] = v - 1
        buf[s[v - 1]] += 1
    for i in range(len(sum_l)): buf[i] = sum_l[i]
    for i in range(n - 1, -1, -1):
      v = sa[i]
      if v >= 1 and ls[v - 1]:
       buf[s[v - 1] + 1] -= 1
       sa[buf[s[v - 1] + 1]] = v - 1

  # なげ～
  lms_map = [-1] * (n + 1)
  m = 0
  for i in range(1, n):
    if not ls[i - 1] and ls[i]:
      lms_map[i] = m
      m += 1
  lms = []
  for i in range(1, n):
    if not ls[i - 1] and ls[i]:
      lms.append(i)

  induce(lms)

  if m:
    sorted_lms = []
    for v in sa:
      if lms_map[v] != -1: sorted_lms.append(v)
    rec_s = [0] * m
    rec_upper = 0
    rec_s[lms_map[sorted_lms[0]]] = 0
    for i in range(1, m):
      l, r = sorted_lms[i - 1], sorted_lms[i]
      end_l = lms[lms_map[l] + 1] if lms_map[l] + 1 < m else n
      end_r = lms[lms_map[r] + 1] if lms_map[r] + 1 < m else n
      same = True
      if end_l - l != end_r - r:
        same = False
      else:
        while l < end_l:
          if s[l] != s[r]: break
          l += 1
          r += 1
        if l == n or s[l] != s[r]: same = False
      if not same: rec_upper += 1
      rec_s[lms_map[sorted_lms[i]]] = rec_upper

    rec_sa = sa_is(rec_s, rec_upper)

    for i in range(m):
      sorted_lms[i] = lms[rec_sa[i]]
    induce(sorted_lms)

  # つかれた
  return sa

# upper以下の配列の接尾辞配列
# O(n + upper だとうれしいな)
def suffix_array(s, upper):
  sa = sa_is(s, upper)
  return sa

# ull以下の配列の接尾辞配列
# O(n log n なのかな）
def suffix_array(s):
  if type(s) == str: return suffix_array_str(s)
  def cmp(r, l):
    return 1 if s[l] < s[r] else -1
  n = len(s)
  idx = [i for i in range(n)]
  idx.sort(key=cmp_to_key(cmp))
  s2 = [0] * n
  now = 0
  for i in range(n):
    if i and s[idx[i - 1]] != s[idx[i]]: now += 1
    s2[idx[i]] = now
  return sa_is(s2, now)

# 文字列の接尾辞配列
# O(n ってマジ？)
def suffix_array_str(s):
  n = len(s)
  s2 = list(map(ord, s))
  return sa_is(s2, 255)

# 最長共通接頭辞配列
# O(n)
def lcp_array(s, sa):
  # 文字列の場合はユニコ頑張ります
  if type(s) == str: s = list(map(ord, s))
  n = len(s)
  rnk = [0] * n
  for i in range(n):
    rnk[sa[i]] = i
  lcp = [0] * (n - 1)
  h = 0
  for i in range(n):
    if h > 0: h -= 1
    if rnk[i] == 0: continue
    j = sa[rnk[i] - 1]
    while j + h < n and i + h < n:
      if s[j + h] != s[i + h]: break
      h += 1
    lcp[rnk[i] - 1] = h
  return lcp

# zアルゴリズム
def z_algorithm(s):
  # 文字はうにこ
  if type(s) == str: s = list(map(ord, s))
  n = len(s)
  if n == 0: return []
  z = [0] * n
  j = 0
  for i in range(1, n):
    # ポインタわからん
    z[i] = 0 if j + z[j] <= i else min(j + z[j] - i, z[i - j])
    while i + z[i] < n and s[z[i]] == s[i + z[i]]: z[i] += 1
    if j + z[j] < i + z[i]: j = i
  z[0] = n
  return z

#-------最強ライブラリここまで------


s = input()

sa = suffix_array(s)
ans = len(s) * (len(s) + 1) // 2
for x in lcp_array(s, sa):
  ans -= x

print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

def SAIS(Sorgin):
    #O(N+sigma)
    #非負数列を入れる
    S = Sorgin + [-1]
    ls = len(S)
    lstable = [1]*ls
    #0ならL-type, 1ならLMSではないS-type, LMSについては何番目に大きいLMSかを格納
    LMS = []
    bucst = [1] + [0]*ls
    cnt = -1
    for i in range(ls-2, -1, -1):
        bucst[S[i]+1] += 1
        if S[i] > S[i+1] or (S[i] == S[i+1] and not lstable[i+1]):
            lstable[i] = 0
            if lstable[i+1]:
                lstable[i+1] = cnt
                cnt -= 1
                LMS.append(i+1)
                
    
    LMS.reverse()
    
    for i in range(ls):
        bucst[i] += bucst[i-1]
    bucen = [bucst[i+1]-1 for i in range(ls)] + [0]
    
    bucst2 = bucst[:]
    bucen2 = bucen[:]
    bucen3 = bucen[:]
    bucen4 = bucen[:]            
    table = [None]*ls
    for idx in LMS:
        table[bucen[S[idx]]] = idx
        bucen[S[idx]] -= 1
    for i in range(ls):
        if not table[i]:
            continue
        # <=> if table[i] == 0 or table[i] is None
        k = table[i]-1
        if not lstable[k]:
            table[bucst[S[k]]] = k
            bucst[S[k]] += 1
    for i in range(ls-1, -1, -1):
        if not table[i]:
            continue
        k = table[i]-1
        if lstable[k]:
            table[bucen2[S[k]]] = k
            bucen2[S[k]] -= 1
    
    table[0] = ls-1
    lmsnum = len(LMS)
    lmssubord = [None]*lmsnum
    lmssubord[0] = ls-1
    lmssublen = [l2-l1+1 for l1, l2 in zip(LMS, LMS[1:])] + [1]
    cnt = 1
    repet = False
    for t in table[1:]:
        if lstable[t] < 0:
            lmssubord[cnt] = t
            cntlen = lmssublen[lstable[t]]
            if cntlen == lmssublen[lstable[lmssubord[cnt-1]]] and S[t:t+cntlen] == S[lmssubord[cnt-1]:lmssubord[cnt-1]+cntlen]:
                repet = True
                lstable[t] = lstable[lmssubord[cnt-1]]
                #ここでlstableはLMSsubstringについて同じものをまとめたものを格納するようになっている
                cnt += 1
                continue
            cnt += 1
    if repet:
        lmssubinv = [None]*ls
        for i in range(lmsnum):
            lmssubinv[lmssubord[i]] = i
        sublst = [lmssubinv[LMS[lstable[t]]] for t in LMS]
        lmssubord = [LMS[r] for r in SAIS(sublst)]
    
    table = [None]*ls
    for idx in lmssubord[::-1]:
        table[bucen3[S[idx]]] = idx
        bucen3[S[idx]] -= 1
    for i in range(ls):
        if not table[i]:
            continue
        # <=> if table[i] == 0 or table[i] is None
        k = table[i]-1
        if not lstable[k]:
            table[bucst2[S[k]]] = k
            bucst2[S[k]] += 1
    for i in range(ls-1, -1, -1):
        if not table[i]:
            continue
        k = table[i]-1
        if lstable[k]:
            table[bucen4[S[k]]] = k
            bucen4[S[k]] -= 1
    return table[1:]

def salcp(S, SAorg):
    N = len(S)
    lcp = [0]*N
    SA = SAorg + [N]
    SAinv = [None]*N
    for i in range(N):
        SAinv[SA[i]] = i
    h = 0
    for i in range(N):
        j = SA[SAinv[i]+1]
        if h:
            h -= 1
        while i+h < N and j+h < N and S[i+h] == S[j+h]:
            h += 1
        lcp[SAinv[i]] = h
    return lcp
         

S = list(map(lambda x: ord(x) - 97, readline().strip()))
N = len(S)

table = [0]*26
for s in S:
    table[s] = 1

table[0] -= 1
for i in range(1, 26):
    table[i] += table[i-1]

S = [table[s] for s in S]

SA = SAIS(S)
LCP = salcp(S, SA)
ans = N*(N+1)//2 - sum(LCP)
print(ans)

Submission status: Accepted

Solution code:
def SA_IS(s, with_lcp = False):
    a = s + [0]
    # a = [aa+1 for aa in a] + [0] # <- 元の列にZeroが含まれるときはこっち
    k = max(a) + 1
    n = len(a)
    
    def induce_l(sa, a, n, k, stype):
        bucket = get_buckets(a, k, 1)
        for i in range(n):
            j = sa[i] - 1
            if j >= 0 and (not stype[j]):
                sa[bucket[a[j]]] = j
                bucket[a[j]] += 1
    
    def induce_s(sa, a, n, k, stype):
        bucket = get_buckets(a, k, 0)
        for i in range(n)[::-1]:
            j = sa[i] - 1
            if j >= 0 and stype[j]:
                bucket[a[j]] -= 1
                sa[bucket[a[j]]] = j
    
    def get_buckets(a, k, start = 0):
        bucket = [0] * k
        for item in a:
            bucket[item] += 1
        s = 0
        for i in range(k):
            s += bucket[i]
            bucket[i] = s - (bucket[i] if start else 0)
        return bucket
    
    def set_lms(a, n, k, default_order):
        bucket = get_buckets(a, k)
        sa = [-1] * n
        for i in default_order[::-1]:
            bucket[a[i]] -= 1
            sa[bucket[a[i]]] = i
        return sa
    
    def induce(a, n, k, stype, default_order):
        sa = set_lms(a, n, k, default_order)
        induce_l(sa, a, n, k, stype)
        induce_s(sa, a, n, k, stype)
        return sa
    
    def rename_LMS_substring(sa, a, n, stype, LMS, l):
        sa = [_s for _s in sa if LMS[_s]]
        tmp = [-1] * (n//2) + [0]
        dupl = 0
        for _ in range(1, l):
            i, j = sa[_-1], sa[_]
            for ii in range(n):
                if a[i+ii] != a[j+ii] or stype[i+ii] != stype[j+ii]:
                    break
                if ii and (LMS[i+ii] or LMS[j+ii]):
                    dupl += 1
                    break
            tmp[j//2] = _ - dupl
        tmp = [t for t in tmp if t >= 0]
        return tmp, dupl
    
    def calc(a, n, k):
        stype = [1] * n
        for i in range(n-1)[::-1]:
            if a[i] > a[i+1] or (a[i] == a[i+1] and stype[i+1] == 0):
                stype[i] = 0
        
        LMS = [1 if stype[i] and not stype[i-1] else 0 for i in range(n-1)] + [1]
        l = sum(LMS)
        lms = [i for i in range(n) if LMS[i]]
        sa = induce(a, n, k, stype, lms)
        renamed_LMS, dupl = rename_LMS_substring(sa, a, n, stype, LMS, l)
        
        if dupl:
            sub_sa = calc(renamed_LMS, l, l - dupl)
        else:
            sub_sa = [0] * l
            for i in range(l):
                sub_sa[renamed_LMS[i]] = i
        
        lms = [lms[sub_sa[i]] for i in range(l)]
        sa = induce(a, n, k, stype, lms)
        return sa
    
    sa = calc(a, n, k)
    sa = sa[1:]
    n -= 1
    if not with_lcp:
        return sa
    
    rank = [0] * n
    for i in range(n):
        rank[sa[i]] = i
    lcp = [0] * (n - 1)
    h = 0
    for i in range(n):
        if h: h -= 1
        if rank[i] == 0: continue
        j = sa[rank[i] - 1]
        while j + h < n and i + h < n:
            if s[j+h] != s[i+h]: break
            h += 1
        lcp[rank[i] - 1] = h
    return sa, lcp

S = [ord(a)-96 for a in input()]
N = len(S)
sa, lcp = SA_IS(S, True)
print(N * (N+1) // 2 - sum(lcp))