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:


class StrAlg:
    @staticmethod
    def sa_naive(s):
        n = len(s)
        sa = list(range(n))
        sa.sort(key=lambda x: s[x:])
        return sa

    @staticmethod
    def sa_doubling(s):
        n = len(s)
        sa = list(range(n))
        rnk = s
        tmp = [0] * n
        k = 1
        while k < n:
            sa.sort(key=lambda x: (rnk[x], rnk[x + k])
                    if x + k < n else (rnk[x], -1))
            tmp[sa[0]] = 0
            for i in range(1, n):
                tmp[sa[i]] = tmp[sa[i - 1]]
                if sa[i - 1] + k < n:
                    x = (rnk[sa[i - 1]], rnk[sa[i - 1] + k])
                else:
                    x = (rnk[sa[i - 1]], -1)
                if sa[i] + k < n:
                    y = (rnk[sa[i]], rnk[sa[i] + k])
                else:
                    y = (rnk[sa[i]], -1)
                if x < y:
                    tmp[sa[i]] += 1
            k *= 2
            tmp, rnk = rnk, tmp
        return sa

    @staticmethod
    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 < 10:
            return StrAlg.sa_naive(s)
        if n < 50:
            return StrAlg.sa_doubling(s)
        ls = [0] * n
        for i in range(n - 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 ls[i]:
                sum_l[s[i] + 1] += 1
            else:
                sum_s[s[i]] += 1
        for i in range(upper):
            sum_s[i] += sum_l[i]
            if i < upper:
                sum_l[i + 1] += sum_s[i]
        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)
        sa = [-1] * n
        buf = sum_s.copy()
        for d in lms:
            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 not ls[v - 1]:
                sa[buf[s[v - 1]]] = v - 1
                buf[s[v - 1]] += 1
        buf = sum_l.copy()
        for i in range(n)[::-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
        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 = 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 = StrAlg.sa_is(rec_s, rec_upper)
            for i in range(m):
                sorted_lms[i] = lms[rec_sa[i]]
            sa = [-1] * n
            buf = sum_s.copy()
            for d in sorted_lms:
                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 not ls[v - 1]:
                    sa[buf[s[v - 1]]] = v - 1
                    buf[s[v - 1]] += 1
            buf = sum_l.copy()
            for i in range(n)[::-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
        return sa

    @staticmethod
    def suffix_array(s, upper=255):
        if type(s) is str:
            s = [ord(c) for c in s]
        return StrAlg.sa_is(s, upper)

    @staticmethod
    def lcp_array(s, sa):
        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

    @staticmethod
    def z_algorithm(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


def atcoder_practice2_i():
    S = input()
    n = len(S)
    ans = (n+1)*n // 2
    sa = StrAlg.suffix_array(S)
    ans -= sum(StrAlg.lcp_array(S, sa))
    print(ans)


if __name__ == "__main__":
    atcoder_practice2_i()

Submission status: Accepted

Solution code:


class StrAlg:
    @staticmethod
    def sa_naive(s):
        n = len(s)
        sa = list(range(n))
        sa.sort(key=lambda x: s[x:])
        return sa

    @staticmethod
    def sa_doubling(s):
        n = len(s)
        sa = list(range(n))
        rnk = s
        tmp = [0] * n
        k = 1
        while k < n:
            sa.sort(key=lambda x: (rnk[x], rnk[x + k])
                    if x + k < n else (rnk[x], -1))
            tmp[sa[0]] = 0
            for i in range(1, n):
                tmp[sa[i]] = tmp[sa[i - 1]]
                x = (rnk[sa[i - 1]], rnk[sa[i - 1] + k]) if sa[i - 1] + \
                    k < n else (rnk[sa[i - 1]], -1)
                y = (rnk[sa[i]], rnk[sa[i] + k]) if sa[i] + \
                    k < n else (rnk[sa[i]], -1)
                if x < y:
                    tmp[sa[i]] += 1
            k *= 2
            tmp, rnk = rnk, tmp
        return sa

    @staticmethod
    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 < 10:
            return StrAlg.sa_naive(s)
        if n < 50:
            return StrAlg.sa_doubling(s)
        ls = [0] * n
        for i in range(n - 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 ls[i]:
                sum_l[s[i] + 1] += 1
            else:
                sum_s[s[i]] += 1
        for i in range(upper):
            sum_s[i] += sum_l[i]
            if i < upper:
                sum_l[i + 1] += sum_s[i]
        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)
        sa = [-1] * n
        buf = sum_s.copy()
        for d in lms:
            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 not ls[v - 1]:
                sa[buf[s[v - 1]]] = v - 1
                buf[s[v - 1]] += 1
        buf = sum_l.copy()
        for i in range(n)[::-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
        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 = 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 = StrAlg.sa_is(rec_s, rec_upper)
            for i in range(m):
                sorted_lms[i] = lms[rec_sa[i]]
            sa = [-1] * n
            buf = sum_s.copy()
            for d in sorted_lms:
                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 not ls[v - 1]:
                    sa[buf[s[v - 1]]] = v - 1
                    buf[s[v - 1]] += 1
            buf = sum_l.copy()
            for i in range(n)[::-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
        return sa

    @staticmethod
    def suffix_array(s, upper=255):
        if type(s) is str:
            s = [ord(c) for c in s]
        return StrAlg.sa_is(s, upper)

    @staticmethod
    def lcp_array(s, sa):
        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

    @staticmethod
    def z_algorithm(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


def atcoder_practice2_i():
    S = input()
    n = len(S)
    ans = (n+1)*n // 2
    sa = StrAlg.suffix_array(S)
    ans -= sum(StrAlg.lcp_array(S, sa))
    print(ans)

if __name__ == "__main__":
    atcoder_practice2_i()

Submission status: Accepted

Solution code:


class StrAlg:
    @staticmethod
    def sa_naive(s):
        n = len(s)
        sa = list(range(n))
        sa.sort(key=lambda x: s[x:])
        return sa

    @staticmethod
    def sa_doubling(s):
        n = len(s)
        sa = list(range(n))
        rnk = s
        tmp = [0] * n
        k = 1
        while k < n:
            sa.sort(key=lambda x: (rnk[x], rnk[x + k])
                    if x + k < n else (rnk[x], -1))
            tmp[sa[0]] = 0
            for i in range(1, n):
                tmp[sa[i]] = tmp[sa[i - 1]]
                x = (rnk[sa[i - 1]], rnk[sa[i - 1] + k]) if sa[i - 1] + \
                    k < n else (rnk[sa[i - 1]], -1)
                y = (rnk[sa[i]], rnk[sa[i] + k]) if sa[i] + \
                    k < n else (rnk[sa[i]], -1)
                if x < y:
                    tmp[sa[i]] += 1
            k *= 2
            tmp, rnk = rnk, tmp
        return sa

    @staticmethod
    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 < 10:
            return StrAlg.sa_naive(s)
        if n < 50:
            return StrAlg.sa_doubling(s)
        ls = [0] * n
        for i in range(n - 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 ls[i]:
                sum_l[s[i] + 1] += 1
            else:
                sum_s[s[i]] += 1
        for i in range(upper):
            sum_s[i] += sum_l[i]
            if i < upper:
                sum_l[i + 1] += sum_s[i]
        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)
        sa = [-1] * n
        buf = sum_s.copy()
        for d in lms:
            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 not ls[v - 1]:
                sa[buf[s[v - 1]]] = v - 1
                buf[s[v - 1]] += 1
        buf = sum_l.copy()
        for i in range(n)[::-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
        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 = 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 = StrAlg.sa_is(rec_s, rec_upper)
            for i in range(m):
                sorted_lms[i] = lms[rec_sa[i]]
            sa = [-1] * n
            buf = sum_s.copy()
            for d in sorted_lms:
                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 not ls[v - 1]:
                    sa[buf[s[v - 1]]] = v - 1
                    buf[s[v - 1]] += 1
            buf = sum_l.copy()
            for i in range(n)[::-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
        return sa

    @staticmethod
    def suffix_array(s, upper=255):
        if type(s) is str:
            s = [ord(c) for c in s]
        return StrAlg.sa_is(s, upper)

    @staticmethod
    def lcp_array(s, sa):
        n = len(s)
        #assert n >= 1
        s2 = [ord(c) for c in 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

    @staticmethod
    def z_algorithm(s):
        n = len(s)
        s2 = [ord(c) for c in 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


def atcoder_practice2_i():
    S = input()
    n = len(S)
    ans = (n+1)*n // 2
    sa = StrAlg.suffix_array(S)
    ans -= sum(StrAlg.lcp_array(S, sa))
    print(ans)

if __name__ == "__main__":
    atcoder_practice2_i()

Submission status: Accepted

Solution code:
# Copy from https://atcoder.jp/contests/practice2/submissions/16808211
# ord: $->36, 0->48, 9->57, A->65, Z->90, a->97, z->122
def suffix_array(s, upper=127):
    n = len(s)
    sa = [-1 for _ in range(n)]
    bucket = [0 for _ in range(upper + 1)]
    smaller = [True for _ in range(n)]
    # leftmost L-type
    is_lms = [False for _ in range(n)]
    lmss = []

    # make indices of buckets
    # range of x's bucket is [bucket[x], bucket[x+1])
    for x in s:
        bucket[x + 1] += 1
    for i in range(upper):
        bucket[i + 1] += bucket[i]

    # step 1:decide whether s[i:n] is a S-type(smaller) or L-type(larger)
    # and whether it's an LMS
    for i in range(n - 2, -1, -1):
        if s[i] > s[i + 1] or (s[i] == s[i + 1] and not smaller[i + 1]):
            smaller[i] = False
            if smaller[i + 1]:
                is_lms[i + 1] = True
                lmss.append(i + 1)

    # step 2-1: fill LMSs from the bottom
    count = [0 for _ in range(upper + 1)]
    for i in lmss:
        sa[bucket[s[i] + 1] - 1 - count[s[i] + 1]] = i
        count[s[i] + 1] += 1

    # step 2-2: fill Ls from the beginning
    count = [0 for _ in range(upper + 1)]
    for i in range(n):
        if sa[i] > 0 and not smaller[sa[i] - 1]:
            sa[bucket[s[sa[i] - 1]] + count[s[sa[i] - 1] + 1]] = sa[i] - 1
            count[s[sa[i] - 1] + 1] += 1

    # step 2-3: fill Ss from the bottom
    count = [0 for _ in range(upper + 1)]
    for i in range(n - 1, -1, -1):
        if sa[i] > 0 and smaller[sa[i] - 1]:
            sa[bucket[s[sa[i] - 1] + 1] - 1 - count[s[sa[i] - 1] + 1]] = sa[i] - 1
            count[s[sa[i] - 1] + 1] += 1

    # step 3: form reduced string from LMS blocks
    new_num = 0
    new_array = [-1 for _ in range(len(lmss))]
    lms_to_ind = dict()
    for i, x in enumerate(lmss):
        lms_to_ind[x] = len(lmss) - 1 - i
    last = sa[0]
    new_array[lms_to_ind[sa[0]]] = 0
    for i in range(1, n):
        if is_lms[sa[i]]:
            tmp, j = sa[i], 0
            while True:
                if s[last + j] != s[tmp + j]:
                    new_num += 1
                    break
                if j > 0 and (is_lms[last + j] or is_lms[tmp + j]):
                    break
                j += 1
            new_array[lms_to_ind[tmp]] = new_num
            last = tmp

    # step 4: sort LMS blocks
    # if all LMS blocks are different, recursion is not needed
    if new_num == len(lmss) - 1:
        seed = [-1 for _ in range(len(lmss))]
        for i, x in enumerate(new_array):
            seed[x] = i
    # call recursive function
    else:
        seed = suffix_array(new_array, upper=new_num + 1)

    new_lmss = [-1 for _ in range(len(lmss))]
    for i, x in enumerate(seed):
        new_lmss[len(lmss) - 1 - i] = lmss[len(lmss) - 1 - x]

    # step 5-1: fill LMSs from the bottom
    sa = [-1 for _ in range(n)]
    count = [0 for _ in range(upper + 1)]
    for i in new_lmss:
        sa[bucket[s[i] + 1] - 1 - count[s[i] + 1]] = i
        count[s[i] + 1] += 1

    # step 5-2: fill Ls from the beginning
    count = [0 for _ in range(upper + 1)]
    for i in range(n):
        if sa[i] > 0 and not smaller[sa[i] - 1]:
            sa[bucket[s[sa[i] - 1]] + count[s[sa[i] - 1] + 1]] = sa[i] - 1
            count[s[sa[i] - 1] + 1] += 1

    # step 5-3: fill Ss from the bottom
    count = [0 for _ in range(upper + 1)]
    for i in range(n - 1, -1, -1):
        if sa[i] > 0 and smaller[sa[i] - 1]:
            sa[bucket[s[sa[i] - 1] + 1] - 1 - count[s[sa[i] - 1] + 1]] = sa[i] - 1
            count[s[sa[i] - 1] + 1] += 1

    return sa


def lcp_array(s, sa):
    n = len(s) - 1
    rank = [-1 for _ in range(n)]
    for i, x in enumerate(sa):
        rank[x] = i
    lcp = [-1 for _ in range(n - 1)]
    i = 0
    for x in rank:
        if x == n - 1:
            continue
        while sa[x] + i < n and sa[x + 1] + i < n and s[sa[x] + i] == s[sa[x + 1] + i]:
            i += 1
        lcp[x] = i
        i = max(0, i - 1)
    return lcp


base = ord('a') - 1
S = [ord(v) - base for v in input().rstrip()] + [0]
N = len(S) - 1
sa = suffix_array(S, 27)[1:]
lcp = lcp_array(S, sa)
print(N * (N + 1) // 2 - sum(lcp))

Submission status: Accepted

Solution code:
#ord: $->36, 0->48, 9->57, A->65, Z->90, a->97, z->122
def SA_IS(s, upper=127):
	n = len(s)
	sa = [-1 for _ in range(n)]
	bucket = [0 for _ in range(upper + 1)]
	smaller = [True for _ in range(n)]
	#leftmost L-type
	is_lms = [False for _ in range(n)]
	lmss = []

	#make indices of buckets
	#range of x's bucket is [bucket[x], bucket[x+1])
	for x in s:
		bucket[x+1] += 1
	for i in range(upper):
		bucket[i+1] += bucket[i]

	#step 1:decide whether s[i:n] is a S-type(smaller) or L-type(larger)
	# and whether it's an LMS
	for i in range(n-2, -1, -1):
		if s[i] > s[i+1] or (s[i] == s[i+1] and not smaller[i+1]):
			smaller[i] = False
			if smaller[i+1]:
				is_lms[i+1] = True
				lmss.append(i+1)

	#step 2-1: fill LMSs from the bottom
	count = [0 for _ in range(upper + 1)]
	for i in lmss:
		sa[bucket[s[i] + 1] - 1 - count[s[i] + 1]] = i
		count[s[i] + 1] += 1

	#step 2-2: fill Ls from the beginning
	count = [0 for _ in range(upper + 1)]
	for i in range(n):
		if sa[i] > 0 and not smaller[sa[i] - 1]:
			sa[bucket[s[sa[i] - 1]] + count[s[sa[i] - 1] + 1]] = sa[i] - 1
			count[s[sa[i] - 1] + 1] += 1

	#step 2-3: fill Ss from the bottom
	count = [0 for _ in range(upper + 1)]
	for i in range(n-1, -1, -1):
		if sa[i] > 0 and smaller[sa[i] - 1]:
			sa[bucket[s[sa[i] - 1] + 1] - 1 - count[s[sa[i] - 1] + 1]] = sa[i] - 1
			count[s[sa[i] - 1] + 1] += 1

	#step 3: form reduced string from LMS blocks
	new_num = 0
	new_array = [-1 for _ in range(len(lmss))]
	lms_to_ind = dict()
	for i, x in enumerate(lmss):
		lms_to_ind[x] = len(lmss) - 1 - i
	last = sa[0]
	new_array[lms_to_ind[sa[0]]] = 0
	for i in range(1, n):
		if is_lms[sa[i]]:
			tmp, j = sa[i], 0
			while True:
				if s[last + j] != s[tmp + j]:
					new_num += 1
					break
				if j > 0 and (is_lms[last + j] or is_lms[tmp + j]):
					break
				j += 1
			new_array[lms_to_ind[tmp]] = new_num
			last = tmp
	
	#step 4: sort LMS blocks
	#if all LMS blocks are different, recursion is not needed
	if new_num == len(lmss) - 1:
		seed = [-1 for _ in range(len(lmss))]
		for i, x in enumerate(new_array):
			seed[x] = i
	#call recursive function
	else:
		seed = SA_IS(new_array, upper=new_num + 1)

	new_lmss = [-1 for _ in range(len(lmss))]
	for i, x in enumerate(seed):
		new_lmss[len(lmss) - 1 - i] = lmss[len(lmss) - 1 - x]

	#step 5-1: fill LMSs from the bottom
	sa = [-1 for _ in range(n)]
	count = [0 for _ in range(upper + 1)]
	for i in new_lmss:
		sa[bucket[s[i] + 1] - 1 - count[s[i] + 1]] = i
		count[s[i] + 1] += 1

	#step 5-2: fill Ls from the beginning
	count = [0 for _ in range(upper + 1)]
	for i in range(n):
		if sa[i] > 0 and not smaller[sa[i] - 1]:
			sa[bucket[s[sa[i] - 1]] + count[s[sa[i] - 1] + 1]] = sa[i] - 1
			count[s[sa[i] - 1] + 1] += 1

	#step 5-3: fill Ss from the bottom
	count = [0 for _ in range(upper + 1)]
	for i in range(n-1, -1, -1):
		if sa[i] > 0 and smaller[sa[i] - 1]:
			sa[bucket[s[sa[i] - 1] + 1] - 1 - count[s[sa[i] - 1] + 1]] = sa[i] - 1
			count[s[sa[i] - 1] + 1] += 1

	return sa


def LCP_Array(s, sa):
	n = len(s)-1
	rank = [-1 for _ in range(n)]
	for i, x in enumerate(sa):
		rank[x] = i
	lcp = [-1 for _ in range(n-1)]
	i = 0
	for x in rank:
		if x == n-1:
			continue
		while sa[x] + i < n and sa[x+1] + i < n and s[sa[x] + i] == s[sa[x+1] + i]:
			i += 1
		lcp[x] = i
		i = max(0, i-1)
	return lcp

s = input()
s = [ord(x)-96 for x in s] + [0]
sa = SA_IS(s, 30)[1:]
lcp = LCP_Array(s, sa)
n = len(s)-1
print(n * (n+1) // 2 - sum(lcp))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
S = input()[: -1]
N = len(S)

def SuffixArray(n, s):
  order = [n - 1 - i for i in range(n)]
  order.sort(key = lambda x: s[x])
  sa = [0] * n
  classes = [0] * n
  for i in range(n):
    sa[i] = order[i]
    classes[i] = S[i]
  k = 1
  while k < n:
    c = classes[: ]
    for i in range(n): 
      if i > 0 and (c[sa[i - 1]] == c[sa[i]]) and ((sa[i - 1] + k) < n) and ((c[sa[i - 1] + k // 2]) == c[sa[i] + k // 2]):
        classes[sa[i]] = classes[sa[i - 1]]
      else: classes[sa[i]] = i
    cc = [i for i in range(n)]
    ss = sa[: ]
    for i in range(n):
      if ss[i] - k >= 0:
        sa[cc[classes[ss[i] - k]]] = ss[i] - k
        cc[classes[ss[i] - k]] += 1
    k <<= 1
  return sa

def LCPArray(n, s, sa):
  r = [0] * n
  for i in range(n): r[sa[i]] = i
  lcp = [0] * (n - 1)
  x = 0
  for i in range(n):
    if x > 0: x -= 1
    if r[i] == 0: continue
    j = sa[r[i] - 1]
    while max(i, j) + x < n:
      if s[i + x] != s[j + x]: break
      x += 1
    lcp[r[i] - 1] = x
  return lcp 
sa = SuffixArray(N, S)
lcp = LCPArray(N, S, sa)
print(N * (N + 1) // 2 - sum(lcp))

Submission status: Accepted

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)

cpdef 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)
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])
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)
"""


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