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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7

# suffix_array, lcp_array
"""
SA-IS Suffix Array Construction
(derived from https://mametter.hatenablog.com/entry/20180130/p1)
Construction of LCP array
(derived from http://www.nct9.ne.jp/m_hiroi/light/pyalgo60.html)
"""
SMALLER = 0
LARGER = 1


def get_ls(seq):
    "smaller: 0, larger: 1"
    N = len(seq)
    ls = [SMALLER] * N
    # sentinel is the smallest
    # ls[-1] = SMALLER

    for i in range(N - 2, -1, -1):
        # s[i] < s[i+1] なら明らかに s[i..] < s[i+1..] => i は S 型
        # s[i] > s[i+1] なら明らかに s[i..] > s[i+1..] => i は L 型
        # s[i] == s[i+1] の場合、s[i..] <=> s[i+1..] の比較結果は
        # s[i+1..] <=> s[i+2..] に準ずる (つまり ls[i + 1] と同じ)
        if seq[i] < seq[i + 1]:
            ls[i] = SMALLER
        elif seq[i] > seq[i + 1]:
            ls[i] = LARGER
        else:
            ls[i] = ls[i + 1]
    return ls


def get_lmss(ls):
    """
    >>> get_lmss(get_ls("mmiissiissiippii$"))
    [2, 6, 10, 16]
    """
    return [i for i in range(len(ls)) if is_lms(ls, i)]


def is_lms(ls, i):
    # インデックス i が LMS かどうか
    return (i > 0 and ls[i - 1] == LARGER and ls[i] == SMALLER)


def sa_is(seq, K=256):
    """
    >>> sa_is(b"mmiissiissiippii$", 256)
    [16, 15, 14, 10, 6, 2, 11, 7, 3, 1, 0, 13, 12, 9, 5, 8, 4]
    >>> sa_is([2, 2, 1, 0], 3)
    [3, 2, 1, 0]
    """
    # L 型か S 型かのテーブル
    ls = get_ls(seq)
    # LMS のインデックスだけを集めた配列
    lmss = get_lmss(ls)
    # 適当な「種」：seed = lmss.shuffle でもよい
    seed = lmss

    # 1 回目の induced sort
    sa = induced_sort(seq, K, ls, seed)

    # induced sort の結果から LMS の suffix だけ取り出す
    sa = [i for i in sa if is_lms(ls, i)]

    # LMS のインデックス i に対して番号 nums[i] を振る
    nums = [None] * len(seq)

    # sa[0] の LMS は $ と決まっているので、番号 0 を振っておく
    nums[sa[0]] = num = 0

    # 隣り合う LMS を比べる
    for index in range(1, len(sa)):
        i = sa[index - 1]
        j = sa[index]
        isDifferent = False
        # 隣り合う LMS 部分文字列の比較
        for d in range(len(seq)):
            if seq[i + d] != seq[j + d] or is_lms(ls, i + d) != is_lms(ls, j + d):
                # LMS 部分文字列の範囲で異なる文字があった
                isDifferent = True
                break
            if d > 0 and (is_lms(ls, i + d) or is_lms(ls, j + d)):
                # LMS 部分文字列の終端に至った
                break
        # 隣り合う LMS 部分文字列が異なる場合は、番号を増やす
        if isDifferent:
            num += 1
        # LMS のインデックス j に番号 num を振る
        nums[j] = num

    # nums の中に出現する番号のみを並べると、LMS 部分文字列を番号に置き換えた列が得られる
    # remove None from nums
    nums = list(filter(lambda x: x is not None, nums))

    if num + 1 < len(nums):
        # 番号の重複があるので再帰
        sa = sa_is(nums, num + 1)
    else:
        # 番号の重複がない場合、suffix array を容易に求められる
        sa = [None] * len(nums)
        for i, c in enumerate(nums):
            sa[c] = i

    # 正しい「種」
    seed = [lmss[i] for i in sa]

    # 2 回目の induced sort
    sa = induced_sort(seq, K, ls, seed)
    return sa


def induced_sort(seq, K, ls, lmss, verbose=False):
    """
    >>> seq = b"mmiissiissiippii$"
    >>> ls = get_ls(seq)
    >>> lmss = get_lmss(ls)
    >>> induced_sort(seq, 256, ls, lmss, verbose=True)
    step1: [16, None, None, None, None, None, 2, 6, 10, None, None, None, None, None, None, None, None]
    step2: [16, 15, 14, None, None, None, 2, 6, 10, 1, 0, 13, 12, 5, 9, 4, 8]
    step3: [16, 15, 14, 10, 2, 6, 11, 3, 7, 1, 0, 13, 12, 5, 9, 4, 8]
    """
    # 作業領域
    sa = [None] * len(seq)

    # seq に出現する文字種ごとのカウント
    count = [0] * K
    for c in seq:
        count[c] += 1

    # 累積和することで bin の境界インデックスを決める
    # 文字種cのbinはbin[c - 1] <= i < bin[c]
    # c is 0-origin
    from itertools import accumulate
    bin = list(accumulate(count)) + [0]

    # ステップ 1: LMS のインデックスをビンの終わりの方から入れる

    # ビンごとにすでに挿入した数をカウントする
    count_in_bin = [0] * K

    for lms in reversed(lmss):
        c = seq[lms]
        # c を入れるビンの終わり (bin[c] - 1) から詰めていれる
        pos = bin[c] - 1 - count_in_bin[c]
        sa[pos] = lms
        count_in_bin[c] += 1

    if verbose:
        print("step1:", sa)

    # ステップ 2: sa を昇順に走査していく

    # ビンごとにすでに挿入した数をカウントする
    count_in_bin = [0] * K

    for i in sa:
        if i is None:
            continue
        if i == 0:
            continue
        if ls[i - 1] == SMALLER:
            continue
        # sa に入っているインデックス i について、i - 1 が L 型であるとき、
        # 文字 seq[i - 1] に対応するビンに i - 1 を頭から詰めていれる
        c = seq[i - 1]
        pos = bin[c - 1] + count_in_bin[c]
        sa[pos] = i - 1
        count_in_bin[c] += 1

    if verbose:
        print("step2:", sa)

    # ステップ 3: sa を逆順に走査していく

    # ビンごとにすでに挿入した数をカウントする
    count_in_bin = [0] * K

    for i in reversed(sa):
        if i is None:
            continue
        if i == 0:
            continue
        if ls[i - 1] == LARGER:
            continue

        # sa に入っているインデックス i について、i - 1 が S 型であるとき、
        # 文字 seq[i - 1] に対応するビンに i - 1 を終わりから詰めていれる
        c = seq[i - 1]
        pos = bin[c] - 1 - count_in_bin[c]
        sa[pos] = i - 1  # 上書きすることもある
        count_in_bin[c] += 1

    if verbose:
        print("step3:", end=" ")

    return sa


def get_height(seq, sa):
    """
    Kasai method
    >>> s = b"banana$"
    >>> sa = sa_is(s, 256)
    >>> get_height(s, sa)
    [0, 1, 3, 0, 0, 2, -1]
    >>> get_height_naive(s, sa) == get_height(s, sa)
    True
    """
    N = len(sa)
    rsa = [0] * N
    for i in range(N):
        rsa[sa[i]] = i

    def lcp(i, j):
        d = 0
        while seq[i + d] == seq[j + d]:
            d += 1
        return d

    height = [0] * N
    h = 0
    for i in range(N):
        j = rsa[i]
        if j == N - 1:  # last
            height[j] = -1
            h = 0
            continue
        k = sa[j + 1]
        if h > 0:
            h = h - 1 + lcp(i + h - 1, k + h - 1)
        else:
            h = lcp(i, k)
        height[j] = h

    return height


def suffix_array(seq, K):
    return sa_is(seq, K)


def lcp_array(seq, sa):
    return get_height(seq, sa)
# ---


def debug(*x):
    print(*x, file=sys.stderr)


def solve(S):
    diff = ord("a") - 1
    N = len(S)
    S = [c - diff for c in S]
    S.append(0)
    lcp = lcp_array(S, suffix_array(S, 27))
    return N * (N + 1) // 2 - sum(lcp) - 1


def main():
    # parse input
    S = input().strip()
    print(solve(S))


# tests
T1 = """
abcbcba
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
21
"""

T2 = """
mississippi
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
53
"""

T3 = """
ababacaca
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
33
"""

T4 = """
aaaaa
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
5
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Runtime Error

Solution code:
def calc_lcp(s1,s2):
    count=0
    for i in range(min(len(s1), len(s2))):
        if s1[i] == s2[i]: count += 1
        else: break
    return count

def suffix_array(s,output_sa=True,output_lcp=True):
    sa = sorted([(i,s[i:]) for i in range(len(s))], key=lambda x: x[1])
    if output_sa and not output_lcp: return sa
    else:
      lcp = [calc_lcp(sa[i-1][1], sa[i][1]) for i in range(1,len(s))]
      if output_sa: return sa,lcp
      else: return lcp

def main():
  S = list(input())
  N = len(S)
  lcp = suffix_array(S,output_sa=False,output_lcp=True)
  print(N*(N+1)//2-sum(lcp))
  
if __name__=="__main__":
  main()

Submission status: Runtime Error

Solution code:
def calc_lcp(s1,s2):
    count=0
    for i in range(min(len(s1), len(s2))):
        if s1[i] == s2[i]: count += 1
        else: break
    return count

def suffix_array(s,output_sa=True,output_lcp=True):
    #sa = sorted([(i,s[i:]) for i in range(len(s))], key=lambda x: x[1])
    sa = [(i,s[i:]) for i in range(len(s))]
    if output_sa and not output_lcp: return sa
    else:
      lcp = [calc_lcp(sa[i-1][1], sa[i][1]) for i in range(1,len(s))]
      if output_sa: return sa,lcp
      else: return lcp

def main():
  S = input()
  N = len(S)
  lcp = suffix_array(S,output_sa=False,output_lcp=True)
  print(N*(N+1)//2-sum(lcp))
  
if __name__=="__main__":
  main()

Submission status: Runtime Error

Solution code:
def calc_lcp(s1,s2):
    count=0
    for i in range(min(len(s1), len(s2))):
        if s1[i] == s2[i]: count += 1
        else: break
    return count

def suffix_array(s,output_sa=True,output_lcp=True):
    sa = sorted([(i,s[i:]) for i in range(len(s))], key=lambda x: x[1])
    if output_sa and not output_lcp: return sa
    else:
      lcp = [calc_lcp(sa[i-1][1], sa[i][1]) for i in range(1,len(s))]
      if output_sa: return sa,lcp
      else: return lcp

def main():
  S = input()
  N = len(S)
  lcp = suffix_array(S,output_sa=False,output_lcp=True)
  print(N*(N+1)//2-sum(lcp))
  
if __name__=="__main__":
  main()

Submission status: Runtime Error

Solution code:
def calc_lcp(s1,s2):
    count=0
    for i in range(min(len(s1), len(s2))):
        if s1[i] == s2[i]: count += 1
        else: break
    return count

def suffix_array(s, lcp=True):
    sa = sorted([(i,s[i:]) for i in range(len(s))], key=lambda x: x[1])
    if lcp: return sa,[calc_lcp(sa[i-1][1], sa[i][1]) for i in range(1,len(s))]
    else: return  sa
    
S = input()
N = len(S)
_,lcp = suffix_array(S)
print(N*(N+1)//2-sum(lcp))

Submission status: Runtime Error

Solution code:
def calc_lcp(s1,s2):
    count=0
    for i in range(min(len(s1), len(s2))):
        if s1[i] == s2[i]: count += 1
        else: break
    return count

def suffix_array(s, lcp=True):
    sa = sorted([(i,s[i:]) for i in range(len(s))], key=lambda x: x[1])
    if lcp: return sa,[calc_lcp(sa[i-1][1], sa[i][1]) for i in range(1,len(s))]
    else: return  sa
    
S = input()
N = len(S)
sa,lcp = suffix_array(S)
print(N*(N+1)//2-sum(lcp))

Submission status: Runtime Error

Solution code:

code = """

# distutils: language=c++
# distutils: include_dirs=[/home/USERNAME/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False

from libcpp.string cimport string
from libcpp.vector cimport vector
from libc.stdio cimport getchar, printf
cdef extern from *:
    ctypedef long long ll "long long"

cdef extern from "<atcoder/string>" namespace "atcoder":
    vector[int] lcp_array(string s, vector[int] sa)
    vector[int] lcp_array[ll](vector[ll] s, vector[int] sa)

def vector[int] LcpArray(string s, vector[int] sa):
    return lcp_array(s, sa)

cpdef vector[int] LcpArrayNum(vector[ll] s, vector[int] sa):
    return lcp_array(s, sa)
cdef extern from *:
    ctypedef long long ll "long long"

cdef extern from "<atcoder/string>" namespace "atcoder":
    vector[int] suffix_array(string s)
    vector[int] suffix_array[ll](vector[ll] s)
    vector[int] suffix_array(vector[int] s, int upper)

cpdef vector[int] SuffixArray(string s):
    return suffix_array(s)

cpdef vector[int] SuffixArrayNum(vector[ll] s):
    return suffix_array(s)

cpdef vector[int] SuffixArrayNumUp(vector[int] s, int upper):
    return suffix_array(s, upper)
cpdef inline vector[int] ReadInt(int n):
    cdef int b, c
    cdef vector[int] *v = new vector[int]()
    for i in range(n):
        c = 0
        while 1:
            b = getchar() - 48
            if b < 0: break
            c = c * 10 + b
        v.push_back(c)
    return v[0]

cpdef inline vector[string] Read(int n):
    cdef char c
    cdef vector[string] *vs = new vector[string]()
    cdef string *s
    for i in range(n):
        s = new string()
        while 1:
            c = getchar()
            if c<=32: break
            s.push_back(c)
        vs.push_back(s[0])
    return vs[0]

cpdef inline void PrintLongN(vector[long] l, int n):
    for i in range(n): printf("%ld\\n", l[i])

cpdef inline void PrintLong(vector[long] l, int n):
    for i in range(n): printf("%ld ", l[i])
"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code = code.replace("USERNAME", getpass.getuser())
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import Read, SuffixArray, LcpArray

def main():
    S = Read(1)[0]
    sa = SuffixArray(S)
    ans = (len(S) * (len(S)+1))//2
    for x in LcpArray(S, sa):
        ans -= x
    print(ans)
if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
def printAllSubstrings(s, n): 
	c=0
	for i in range(n): 

        temp="" 

        for j in range(i,n): 

            temp+=s[j] 

            c+=1
	print(c)

  

# Driver program to test above function 

  

s = input()

AllSubstrings(s, len(s))

Submission status: Runtime Error

Solution code:
def printAllSubstrings(s, n): 

  

    # Fix start index in outer 
    c=0

    for i in range(n): 

        temp="" 

        for j in range(i,n): 

            temp+=s[j] 

            c+=1
     print(c)
        

  
# Driver program to test above function 

  

s = input()

printAllSubstrings(s, len(s))

Submission status: Runtime Error

Solution code:
# Date [ 2020-09-09 19: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(l, r):
        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(x, y):
        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
        sa = [-1] * n
        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; sa[buf[s[v - 1]]] = v - 1
        buf.clear()

    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 = [-1] * 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()