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

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


"""
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
    
    

    for i in range(N - 2, -1, -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):
    
    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]
    """
    
    ls = get_ls(seq)
    
    lmss = get_lmss(ls)
    
    seed = lmss

    
    sa = induced_sort(seq, K, ls, seed)

    
    sa = [i for i in sa if is_lms(ls, i)]

    
    nums = [None] * len(seq)

    
    nums[sa[0]] = num = 0

    
    for index in range(1, len(sa)):
        i = sa[index - 1]
        j = sa[index]
        isDifferent = False
        
        for d in range(len(seq)):
            if seq[i + d] != seq[j + d] or is_lms(ls, i + d) != is_lms(ls, j + d):
                
                isDifferent = True
                break
            if d > 0 and (is_lms(ls, i + d) or is_lms(ls, j + d)):
                
                break
        
        if isDifferent:
            num += 1
        
        nums[j] = num

    
    
    nums = list(filter(lambda x: x is not None, nums))

    if num + 1 < len(nums):
        
        sa = sa_is(nums, num + 1)
    else:
        
        sa = [None] * len(nums)
        for i, c in enumerate(nums):
            sa[c] = i

    
    seed = [lmss[i] for i in sa]

    
    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)

    
    count = [0] * K
    for c in seq:
        count[c] += 1

    
    
    
    from itertools import accumulate
    bin = list(accumulate(count)) + [0]

    

    
    count_in_bin = [0] * K

    for lms in reversed(lmss):
        c = seq[lms]
        
        pos = bin[c] - 1 - count_in_bin[c]
        sa[pos] = lms
        count_in_bin[c] += 1

    if verbose:
        print("step1:", 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
        
        
        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)

    

    
    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

        
        
        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:  
            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():
    
    S = input().strip()
    print(solve(S))



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

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


"""
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
    
    

    for i in range(N - 2, -1, -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):
    
    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]
    """
    
    ls = get_ls(seq)
    
    lmss = get_lmss(ls)
    
    seed = lmss

    
    sa = induced_sort(seq, K, ls, seed)

    
    sa = [i for i in sa if is_lms(ls, i)]

    
    nums = [None] * len(seq)

    
    nums[sa[0]] = num = 0

    
    for index in range(1, len(sa)):
        i = sa[index - 1]
        j = sa[index]
        isDifferent = False
        
        for d in range(len(seq)):
            if seq[i + d] != seq[j + d] or is_lms(ls, i + d) != is_lms(ls, j + d):
                
                isDifferent = True
                break
            if d > 0 and (is_lms(ls, i + d) or is_lms(ls, j + d)):
                
                break
        
        if isDifferent:
            num += 1
        
        nums[j] = num

    
    
    nums = list(filter(lambda x: x is not None, nums))

    if num + 1 < len(nums):
        
        sa = sa_is(nums, num + 1)
    else:
        
        sa = [None] * len(nums)
        for i, c in enumerate(nums):
            sa[c] = i

    
    seed = [lmss[i] for i in sa]

    
    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)

    
    count = [0] * K
    for c in seq:
        count[c] += 1

    
    
    
    from itertools import accumulate
    bin = list(accumulate(count)) + [0]

    

    
    count_in_bin = [0] * K

    for lms in reversed(lmss):
        c = seq[lms]
        
        pos = bin[c] - 1 - count_in_bin[c]
        sa[pos] = lms
        count_in_bin[c] += 1

    if verbose:
        print("step1:", 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
        
        
        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)

    

    
    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

        
        
        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:  
            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():
    
    S = input().strip()
    print(solve(S))



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