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: Time Limit Exceeded

Solution code:
# import sys; input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class SuffixArray:
	def __init__(self, S):
		self.S = S
		self.N = len(S)

	# 接尾辞配列(SA)をリスト(数値)で返す
	def suffix(self):
		S = self.S; N = self.N
		SA = [0] * (N + 1)
		rank = [0] * (N + 1); rankNex = [0] * (N + 1)
		for i in range(N + 1):
			SA[i] = i
			rank[i] = ord(S[i]) if i < N else -1

		# ダブリングしながら計算していく
		k = 1
		cmp_key = lambda e: (rank[e], rank[e + k] if e + k <= N else -1)
		while k <= N:
			SA.sort(key = cmp_key)
			rankNex[SA[0]] = 0
			# 隣接する接尾辞の比較
			for i in range(1, N + 1):
				rankNex[SA[i]] = rankNex[SA[i-1]] + (cmp_key(SA[i - 1])<cmp_key(SA[i]))
			#rankの更新
			for i in range(N + 1):
				rank[i] = rankNex[i]
			k *= 2

		self.SA = SA
		return SA

	# 高さ配列(LCP Array)をリスト(数値)で返す
	def lcp(self):
		N = self.N; S = self.S; SA = self.SA
		LCP = [-1] * (N + 1); rank = [0] * (N + 1)
		for i in range(N + 1):
			rank[SA[i]] = i

		# 文字列の長い順から、尺取り法の要領で文字列比較+LCPの計算
		h = 0; LCP[0] = 0
		for i in range(N):
			j = SA[rank[i] - 1]
			if h > 0:
				h -= 1
			while j + h < N and i + h < N and S[j + h] == S[i + h]:
				h += 1
			LCP[rank[i] - 1] = h
		
		self.LCP = LCP
		return LCP

class SegmentTree(object):
	#N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.N0 = 2 ** (N - 1).bit_length()
		self.data = [INF] * (2 * self.N0)

	#list = [x0, x1, x2, ... xN-1]で初期化
	def initialize(self, L):
		N = self.N; N0 = self.N0
		for i in range(N):
			self.data[N0 - 1 + i] = L[i]
		for i in range(N0 - 2, -1, -1):
			self.data[i] = min(self.data[2 * i + 1], self.data[2 * i + 2])
		
	#区間[l, r]の最小値
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = INF
		while L < R:
			if R & 1:
				R -= 1
				m = min(m, self.data[R - 1])
			if L & 1:
				m = min(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return m

def main():
	S = input(); N = len(S)
	Suf = SuffixArray(S)
	SA = Suf.suffix()
	LCP = Suf.lcp()

	ans = 0
	for i in range(N):
		ans += max(0, (N - SA[i + 1]) - LCP[i])

	print(ans) 




if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
class SuffixArray:
    def __init__(self, S):
        self.N = len(S)
        self.S = S
        self.sa = self.__make_sa()
        self.lcp, self.rank = self.__make_lcp()

    @staticmethod
    def atoi(a):
        return ord(a) - ord("a") + 1

    def show(self):
        for i in range(self.N + 1):
            print(i, self.sa[i], self.lcp[i], self.S[self.sa[i]:])

    def __make_sa(self):
        """配列（文字列）Sのsuffix arrayを返す O(N(logN)^2)"""
        N = self.N
        SA = list(range(N + 1))
        rank = [-1] * (N + 1)
        tmp = [0] * (N + 1)
        k = 1

        for i, s in enumerate(self.S):
            rank[i] = self.atoi(s)

        def key(i):
            if i + k <= N:
                return (rank[i], rank[i + k])
            return (rank[i], -1)

        def cmp(i, j):
            return key(i) < key(j)

        while k <= N:
            SA.sort(key=key)
            tmp[SA[0]] = 0
            for i in range(1, N + 1):
                tmp[SA[i]] = tmp[SA[i - 1]] + cmp(SA[i - 1], SA[i])
            for i in range(N + 1):
                rank[i] = tmp[i]
            k *= 2
        return SA

    def __make_lcp(self):
        lcp = [0] * (self.N + 1)
        rank = [0] * (self.N + 1)
        for i in range(self.N + 1):
            rank[self.sa[i]] = i
        h = 0
        for i in range(self.N):
            j = self.sa[rank[i] - 1]
            if h > 0:
                h -= 1
            while j + h < self.N and i + h < self.N:
                if self.S[i + h] != self.S[j + h]:
                    break
                h += 1
            lcp[rank[i] - 1] = h
        return lcp, rank

    def contain(self, T, side="left"):
        """文字列SにTが含まれているかを返すO(|T|log|S|)
        input
            T: 検索する文字列（配列）
            side: left　-> S[sa[i]:sa[i]+NT] == Tとなる最小のindex iを返す
                  right -> 最大のindexを返す
        output:
            含まれる場合: S[sa[i]: sa[i]+NT] == Tとなる最小or最大のi
            含まれない場合: -1
        """
        NT = len(T)
        if NT > self.N:
            return -1
        L = 0
        R = self.N
        if side == "left":
            while R - L > 1:
                m = (L + R) // 2
                i = self.sa[m]
                if self.S[i:i + NT] < T:
                    L = m
                else:
                    R = m
            i = self.sa[R]
            if self.S[i:i + NT] == T:
                return R
        else:
            R += 1
            while R - L > 1:
                m = (L + R) // 2
                i = self.sa[m]
                if self.S[i:i + NT] <= T:
                    L = m
                else:
                    R = m
            i = self.sa[L]
            if self.S[i:i + NT] == T:
                return L
        return -1

    def get_indices(self, T):
        """Sの中に含まれるTの位置を格納したindexのリストを返す"""
        L = self.contain(T, side="left")
        if L == -1:
            return []
        R = self.contain(T, side="right")
        return [self.sa[i] for i in range(L, R+1)]


S = input()
N = len(S)
SA = SuffixArray(S)

ans = 0
for x, y in zip(SA.sa[1:], SA.lcp):
    ans += N - x - y

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

class SuffixArray:

    class SparseTable:

        def __init__(self, A, func):
            self.N = len(A)
            self.func = func
            h = 0
            while 1<<h <= self.N:
                h += 1
            self.dat = list2d(h, 1<<h, 0)
            self.height = [0] * (self.N+1)

            for i in range(2, self.N+1):
                self.height[i] = self.height[i>>1] + 1
            for i in range(self.N):
                self.dat[0][i] = A[i]
            for i in range(1, h):
                for j in range(self.N):
                    self.dat[i][j] = self.func(self.dat[i-1][j], self.dat[i-1][min(j+(1<<(i-1)), self.N-1)])
            
        def get(self, l, r):
            """ 区間[l,r)でのmin,maxを取得 """

            if l >= r:
                raise Exception
            a = self.height[r-l]
            return self.func(self.dat[a][l], self.dat[a][r-(1<<a)])

    def __init__(self, S):
        self.k = 1
        if S and type(S[0]) == str:
            self.S = [ord(s) for s in S]
        else:
            self.S = S
        self.N = len(S)
        self.rank = [0] * (self.N+1)
        self.tmp = [0] * (self.N+1)
        self.sa = [0] * (self.N+1)
        self.build_sa()

    # def compare_sa(self, i, j):
    #     if self.rank[i] != self.rank[j]:
    #         return self.rank[i] < self.rank[j]
    #     else:
    #         ri = self.rank[i+self.k] if i + self.k <= self.N else -1
    #         rj = self.rank[j+self.k] if j + self.k <= self.N else -1
    #         return ri < rj

    def compare_sa(self, i, j):
        """ saの比較関数 """

        # 第1キー
        if self.rank[i] == self.rank[j]: res1 =  0
        elif self.rank[i] < self.rank[j]: res1 =  -1
        else: res1 = 1
        # 第2キー
        ri = self.rank[i+self.k] if i + self.k <= self.N else -1
        rj = self.rank[j+self.k] if j + self.k <= self.N else -1
        if ri == rj: res2 = 0
        elif ri < rj: res2 = -1
        else: res2 = 1
        # 比較
        return res1 or res2

    def build_sa(self):
        """ Suffix Arrayの構築 """
        from functools import cmp_to_key

        # 最初は1文字、ランクは文字コード
        for i in range(self.N+1):
            self.sa[i] = i
            self.rank[i] = self.S[i] if i < self.N else -1
    
        # k文字についてソートされているところから、2k文字でソートする
        k = 1
        while k <= self.N:
            self.k = k
            self.sa = sorted(self.sa, key=cmp_to_key(self.compare_sa))
            k *= 2

            # いったんtmpに次のランクを計算し、それからrankに移す
            self.tmp[self.sa[0]] = 0
            for i in range(1, self.N+1):
                self.tmp[self.sa[i]] = self.tmp[self.sa[i-1]] + (1 if self.compare_sa(self.sa[i-1], self.sa[i]) else 0)
            for i in range(self.N+1):
                self.rank[i] = self.tmp[i]

        # 文字列が陽に持てる量ならこっちのが速い
        # from operator import itemgetter

        # suffix_arr = [(self.S[i:], i) for i in range(self.N+1)]
        # suffix_arr.sort(key=itemgetter(0))
        # for i in range(self.N+1):
        #     self.sa[i] = suffix_arr[i][1]

    def build_lcp(self):
        """ LCP配列の構築 """

        self.lcp = [0] * (self.N+1)
        self.rsa = [0] * (self.N+1)
        for i in range(self.N+1):
            self.rsa[self.sa[i]] = i
        h = 0
        self.lcp[0] = 0
        for i in range(self.N):
            # 文字列内での位置iの接尾辞と、接尾辞配列内でその1つ前の接尾辞のLCPを求める
            j = self.sa[self.rsa[i]-1]

            # hを先頭の分1減らし、後ろが一致しているだけ増やす
            if h > 0:
                h -= 1
            while j+h < self.N and i+h < self.N:
                if self.S[j+h] != self.S[i+h]:
                    break
                h += 1
            self.lcp[self.rsa[i]-1] = h

    def build_st(self):
        """ 区間取得のためSparseTableを構築 """

        self.st = self.SparseTable(self.lcp, min)

    def getLCP(self, i, j):
        """ S[i:]とS[j:]の共通文字数を取得 """

        return self.st.get(min(self.rsa[i], self.rsa[j]), max(self.rsa[i], self.rsa[j]))

S = input()
N = len(S)

sa = SuffixArray(S)
sa.build_lcp()

ans = N*(N+1) // 2
for i in range(N):
    ans -= sa.lcp[i]
print(ans)

Submission status: Accepted

Solution code:
def sa_naive(s: list):
    n = len(s)
    sa = list(range(n))
    sa.sort(key=lambda x: s[x:])
    return sa


def sa_doubling(s: list):
    n = len(s)
    n_plus = n + 10
    sa = list(range(n))
    rnk = s[::]
    tmp = [0] * n
    k = 1
    while(k < n):
        def cmp(x):
            first = rnk[x] * n_plus
            second = -1 if (x + k >= n) else rnk[x + k]
            return first + second
        sa.sort(key=cmp)
        tmp[sa[0]] = 0
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i]) > cmp(sa[i - 1]))
        rnk, tmp = tmp, rnk
        k *= 2
    return sa


def sa_is(s: list, upper: int):
    THRESHOLD_NAIVE = 10
    THRESHOLD_DOUBLING = 40

    n = len(s)
    if(n == 0):
        return []
    elif(n == 1):
        return [0]
    elif(n == 2):
        if(s[0] < s[1]):
            return [0, 1]
        else:
            return [1, 0]

    if(n < THRESHOLD_NAIVE):
        return sa_naive(s)
    elif(n < THRESHOLD_DOUBLING):
        return sa_doubling(s)

    sa = [0] * n
    ls = [0] * 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):
        sum_s[i] += sum_l[i]
        if(i < upper):
            sum_l[i + 1] += sum_s[i]

    def induce(lms: list):
        nonlocal sa, sum_s, sum_l
        sa = [-1] * n
        buf = sum_s[::]
        for d in lms:
            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) & (not ls[v - 1]):
                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) & (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]) & (ls[i]):
            lms_map[i] = m
            m += 1
    lms = []
    for i in range(1, n):
        if(not ls[i - 1]) & (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:i + 1]
            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):
                    same = False
                elif(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, upper: int = -1):
    n = len(s)
    if(type(s) is list) & (upper >= 0):
        assert (0 <= min(s)) & (max(s) <= upper)
        return sa_is(s, upper)

    elif(type(s) is list) & (upper == -1):
        idx = list(range(n))
        idx.sort(key=lambda x: s[x])
        s2 = [0] * n
        now = 0
        s2[idx[0]] = now
        for i in range(1, n):
            if(s[idx[i - 1]] != s[idx[i]]):
                now += 1
            s[idx[i]] = now
        return sa_is(s2, now)

    elif(type(s) is str):
        s2 = [0] * n
        for i, si in enumerate(s):
            s2[i] = ord(si)
        return sa_is(s2, max(s2))

    else:
        print('type error')
        assert 0 == 1


def lcp_array(s, sa: list):
    n = len(s)
    assert n >= 1
    if(type(s) is str):
        s2 = [0] * n
        for i, si in enumerate(s):
            s2[i] = ord(si)
        s = s2

    rnk = [0] * n
    for i, sai in enumerate(sa):
        rnk[sai] = 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) & (i+h < n):
            if(s[j+h] != s[i+h]):
                break
            h += 1
        lcp[rnk[i] - 1] = h
    return lcp

s = input()
n = len(s)
sa = suffix_array(s)
la = lcp_array(s,sa)
ans = n*(n+1)//2 - sum(la)
print(ans)

Submission status: Accepted

Solution code:
import copy
import functools
import typing


def _sa_naive(s: typing.List[int]) -> typing.List[int]:
    sa = list(range(len(s)))
    return sorted(sa, key=lambda i: s[i:])


def _sa_doubling(s: typing.List[int]) -> typing.List[int]:
    n = len(s)
    sa = list(range(n))
    rnk = copy.deepcopy(s)
    tmp = [0] * n
    k = 1
    while k < n:
        def cmp(x: int, y: int) -> bool:
            if rnk[x] != rnk[y]:
                return rnk[x] - rnk[y]
            rx = rnk[x + k] if x + k < n else -1
            ry = rnk[y + k] if y + k < n else -1
            return rx - ry
        sa.sort(key=functools.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 - 1], sa[i]) else 0)
        tmp, rnk = rnk, tmp
        k *= 2
    return sa


def _sa_is(s: typing.List[int], upper: int) -> typing.List[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_naive = 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_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):
        if s[i] == s[i + 1]:
            ls[i] = ls[i + 1]
        else:
            ls[i] = 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: typing.List[int]) -> None:
        nonlocal sa
        sa = [-1] * n

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

        buf = copy.deepcopy(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.deepcopy(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 = []
    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):
            left = sorted_lms[i - 1]
            right = sorted_lms[i]
            if lms_map[left] + 1 < m:
                end_l = lms[lms_map[left] + 1]
            else:
                end_l = n
            if lms_map[right] + 1 < m:
                end_r = lms[lms_map[right] + 1]
            else:
                end_r = n

            same = True
            if end_l - left != end_r - right:
                same = False
            else:
                while left < end_l:
                    if s[left] != s[right]:
                        break
                    left += 1
                    right += 1
                if left == n or s[left] != s[right]:
                    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: typing.Union[str, typing.List[int]],
                 upper: typing.Optional[int] = None) -> typing.List[int]:
    if isinstance(s, str):
        return _sa_is([ord(c) for c in s], 255)
    elif upper is None:
        n = len(s)
        idx = list(range(n))
        idx.sort(key=functools.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)
    else:
        assert 0 <= upper
        for d in s:
            assert 0 <= d <= upper

        return _sa_is(s, upper)


def lcp_array(s: typing.Union[str, typing.List[int]],
              sa: typing.List[int]) -> typing.List[int]:
    '''
    Reference:
    T. Kasai, G. Lee, H. Arimura, S. Arikawa, and K. Park,
    Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its
    Applications
    '''

    if isinstance(s, str):
        s = [ord(c) for c in s]

    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 z_algorithm(s: typing.Union[str, typing.List[int]]) -> typing.List[int]:
    '''
    Reference:
    D. Gusfield,
    Algorithms on Strings, Trees, and Sequences: Computer Science and
    Computational Biology
    '''

    if isinstance(s, str):
        s = [ord(c) for c in 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()
N = len(S)

sa = suffix_array(S)
lcp = lcp_array(S,sa)

res = N*(N+1)//2
for tmp in lcp:
    res -= tmp

print(res)

Submission status: Accepted

Solution code:
# # https://github.com/not522/ac-library-python/blob/master/atcoder/string.py

import copy
import functools
import typing


def _sa_naive(s: typing.List[int]) -> typing.List[int]:
    sa = list(range(len(s)))
    return sorted(sa, key=lambda i: s[i:])


def _sa_doubling(s: typing.List[int]) -> typing.List[int]:
    n = len(s)
    sa = list(range(n))
    rnk = copy.deepcopy(s)
    tmp = [0] * n
    k = 1
    while k < n:
        def cmp(x: int, y: int) -> bool:
            if rnk[x] != rnk[y]:
                return rnk[x] - rnk[y]
            rx = rnk[x + k] if x + k < n else -1
            ry = rnk[y + k] if y + k < n else -1
            return rx - ry
        sa.sort(key=functools.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 - 1], sa[i]) else 0)
        tmp, rnk = rnk, tmp
        k *= 2
    return sa


def _sa_is(s: typing.List[int], upper: int) -> typing.List[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_naive = 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_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):
        if s[i] == s[i + 1]:
            ls[i] = ls[i + 1]
        else:
            ls[i] = 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: typing.List[int]) -> None:
        nonlocal sa
        sa = [-1] * n

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

        buf = copy.deepcopy(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.deepcopy(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 = []
    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):
            left = sorted_lms[i - 1]
            right = sorted_lms[i]
            if lms_map[left] + 1 < m:
                end_l = lms[lms_map[left] + 1]
            else:
                end_l = n
            if lms_map[right] + 1 < m:
                end_r = lms[lms_map[right] + 1]
            else:
                end_r = n

            same = True
            if end_l - left != end_r - right:
                same = False
            else:
                while left < end_l:
                    if s[left] != s[right]:
                        break
                    left += 1
                    right += 1
                if left == n or s[left] != s[right]:
                    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: typing.Union[str, typing.List[int]],
                 upper: typing.Optional[int] = None) -> typing.List[int]:
    if isinstance(s, str):
        return _sa_is([ord(c) for c in s], 255)
    elif upper is None:
        n = len(s)
        idx = list(range(n))
        idx.sort(key=functools.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)
    else:
        assert 0 <= upper
        for d in s:
            assert 0 <= d <= upper

        return _sa_is(s, upper)


def lcp_array(s: typing.Union[str, typing.List[int]],
              sa: typing.List[int]) -> typing.List[int]:
    '''
    Reference:
    T. Kasai, G. Lee, H. Arimura, S. Arikawa, and K. Park,
    Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its
    Applications
    '''

    if isinstance(s, str):
        s = [ord(c) for c in s]

    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
  
s = input()
sa = suffix_array(s)

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