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: Wrong Answer

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

from functools import cmp_to_key
import copy 
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 - 1], sa[i]) 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 = 1 * len(s) * (len(s) + 1) // 2
for x in lcp_array(s, sa):
  ans -= x

print(ans)

Submission status: Wrong Answer

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)

leng = [N-sa for sa in SA]

ans = sum(l*(l+1)//2 for l in leng) - sum(c*(c+1)//2 for c in LCP)
print(ans)

Submission status: Time Limit Exceeded

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

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)]
    is_lms = [False for _ in range(n)]
    lmss = []

    for x in s:
        bucket[x+1] += 1
    for i in range(upper):
        bucket[i+1] += bucket[i]
    
    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)

    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

    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

    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

    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
            
    if new_num == len(lmss) - 1:
        seed = [-1 for _ in range(len(lmss))]
        for i, x in enumerate(new_array):
            seed[x] = i

    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]

    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

    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

    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 suffix_array(s):
    lis = [ord(x)-96 for x in s] + [0]
    sa = SA_IS(lis, 30)[1:]
    return sa

def main():
    s = input()[:-1]
    n = len(s)
    sa = suffix_array(s)

    
    ans = 0
    for i in range(n):
        v = sa[i]
        ans += n - v
        if i == 0:
            continue
        
        w = sa[i-1]
        l, r = 0, min(n-v, n-w)
        while r - l > 1:
            k = (r + l) // 2
            if s[v:v+k] == s[w:w+k]:
                l = k
            else:
                r = k
        
        if s[v:v+r] == s[w:w+r]:
            ans -= r
        else:
            ans -= l
    
    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    # O(NlogN)
    # return suffix array and lcp array
    # 0th index of SA is |S|
    def SuffixArray(S):
        S = S + "$"
        N = len(S)
        LV = N.bit_length()

        # 0th sort
        P = []
        C = [0] * N
        cnt = [[] for _ in range(256)]
        for i, s in enumerate(S):
            cnt[ord(s)].append(i)
        cnt_c = 0
        for i_list in cnt:
            for i in i_list:
                P.append(i)
                C[i] = cnt_c
            if i_list:
                cnt_c += 1

        # doubling
        for k in range(LV):
            P_new = []
            C_new = [0] * N
            cnt = [[] for _ in range(N)]
            k2 = 1 << k
            for i in range(N):
                P[i] = P[i] - k2
                if P[i] < 0:
                    P[i] += N
                cnt[C[P[i]]].append(P[i])
            for i_list in cnt:
                P_new.extend(i_list)
            cnt_c = -1
            prev = None
            for p in P_new:
                p_ = p + k2
                if p_ >= N:
                    p_ -= N
                new = C[p] * N + C[p_]
                if new != prev:
                    cnt_c += 1
                    prev = new
                C_new[p] = cnt_c
            P = P_new
            C = C_new

        # lcp
        rank = [0] * N
        for i in range(N):
            rank[P[i]] = i
        LCP = [0] * (N - 1)
        h = 0
        for i in range(N - 1):
            j = P[rank[i] - 1]
            if h > 0:
                h -= 1
            while i + h < N and j + h < N:
                if S[i + h] == S[j + h]:
                    h += 1
                else:
                    break
            LCP[rank[i] - 1] = h

        return P, LCP

    S = input().rstrip('\n')
    N = len(S)
    SA, LCP = SuffixArray(S)
    print(N * (N+1) // 2 - sum(LCP))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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)]
    is_lms = [False for _ in range(n)]
    lmss = []

    for x in s:
        bucket[x+1] += 1
    for i in range(upper):
        bucket[i+1] += bucket[i]
    
    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)

    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

    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

    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

    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
            
    if new_num == len(lmss) - 1:
        seed = [-1 for _ in range(len(lmss))]
        for i, x in enumerate(new_array):
            seed[x] = i

    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]

    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

    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

    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 suffix_array(s):
    lis = [ord(x)-96 for x in s] + [0]
    sa = SA_IS(lis, 30)[1:]
    return sa

def main():
    s = input()[:-1]
    n = len(s)
    sa = suffix_array(s)

    
    ans = 0
    for i in range(n):
        v = sa[i]
        ans += n - v
        if i == 0:
            continue
        
        w = sa[i-1]
        for j in range(min(n-v, n-w)):
            if s[v+j] == s[w+j]:
                ans -= 1
            else:
                break
    
    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    # O(NlogN)
    # return suffix array and lcp array
    # 0th index of SA is |S|
    def SuffixArray(S):
        S = S + "$"
        N = len(S)
        LV = N.bit_length()

        # 0th sort
        P = []
        C = [0] * N
        cnt = [[] for _ in range(256)]
        for i, s in enumerate(S):
            cnt[ord(s)].append(i)
        cnt_c = 0
        for i_list in cnt:
            for i in i_list:
                P.append(i)
                C[i] = cnt_c
            if i_list:
                cnt_c += 1

        # doubling
        for k in range(LV):
            P_new = []
            C_new = [0] * N
            cnt = [[] for _ in range(N)]
            k2 = 1 << k
            for i in range(N):
                P[i] = (P[i] - k2) % N
                cnt[C[P[i]]].append(P[i])
            for i_list in cnt:
                for i in i_list:
                    P_new.append(i)
            cnt_c = -1
            prev = -1
            for p in P_new:
                new = C[p] * N + C[(p + k2) % N]
                if new != prev:
                    cnt_c += 1
                    prev = new
                C_new[p] = cnt_c
            P = P_new
            C = C_new

        # lcp
        rank = [0] * N
        for i in range(N):
            rank[P[i]] = i
        LCP = [0] * (N - 1)
        h = 0
        for i in range(N - 1):
            j = P[rank[i] - 1]
            if h > 0:
                h -= 1
            while i + h < N and j + h < N:
                if S[i + h] == S[j + h]:
                    h += 1
                else:
                    break
            LCP[rank[i] - 1] = h

        return P, LCP

    S = input().rstrip('\n')
    N = len(S)
    SA, LCP = SuffixArray(S)
    print(N * (N+1) // 2 - sum(LCP))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    # O(NlogN)
    # return suffix array and lcp array
    # 0th index of SA is |S|
    def SuffixArray(S):
        S = S + "$"
        N = len(S)
        LV = N.bit_length()

        # 0th sort
        P = []
        C = [0] * N
        cnt = [[] for _ in range(256)]
        for i, s in enumerate(S):
            cnt[ord(s)].append(i)
        cnt_c = 0
        for i_list in cnt:
            for i in i_list:
                P.append(i)
                C[i] = cnt_c
            if i_list:
                cnt_c += 1

        # doubling
        for k in range(LV):
            P_new = []
            C_new = [0] * N
            cnt = [[] for _ in range(N)]
            for i in range(N):
                P[i] = (P[i] - (1 << k)) % N
                cnt[C[P[i]]].append(P[i])
            for i_list in cnt:
                for i in i_list:
                    P_new.append(i)
            cnt_c = -1
            prev = -1
            for p in P_new:
                new = C[p] * N + C[(p + (1 << k)) % N]
                if new != prev:
                    cnt_c += 1
                    prev = new
                C_new[p] = cnt_c
            P = P_new
            C = C_new

        # lcp
        rank = [0] * N
        for i in range(N):
            rank[P[i]] = i
        LCP = [0] * (N - 1)
        h = 0
        for i in range(N - 1):
            j = P[rank[i] - 1]
            if h > 0:
                h -= 1
            while i + h < N and j + h < N:
                if S[i + h] == S[j + h]:
                    h += 1
                else:
                    break
            LCP[rank[i] - 1] = h

        return P, LCP

    S = input().rstrip('\n')
    N = len(S)
    SA, LCP = SuffixArray(S)
    print(N * (N+1) // 2 - sum(LCP))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class DisjointSparseTable:
    def __init__(self, a, op=lambda a, b: max(a, b), e=0):
        # Operator
        self.op = op
        # Identity element
        self.e = e
        self.n = len(a)
        self.level = (self.n - 1).bit_length()
        self.size = 2 ** self.level
        self.table = [[self.e] * self.size for _ in range(self.level)]
        # Set bottom first
        for i, item in enumerate(a):
            self.table[-1][i] = item
        self.build()

    def build(self):
        for i in range(1, self.level):
            step = 2 ** i
            lv = self.level - 1 - i
            for mid in range(step, self.n + step, step * 2):
                # Forward
                val = self.e
                for j in range(step):
                    val = self.op(val, self.table[-1][mid + j])
                    self.table[lv][mid + j] = val
                # Backward
                val = self.e
                for j in range(step):
                    val = self.op(self.table[-1][mid - 1 - j], val)
                    self.table[lv][mid - 1 - j] = val

    # Returns f[l:r)
    def fold(self, l, r):
        if l == r:
            return self.e
        elif l == r - 1:
            return self.table[-1][l]
        lv = self.level - (l ^ r - 1).bit_length()
        return self.op(self.table[lv][l], self.table[lv][r - 1])


class SuffixArray:
    def __init__(self, S):
        a = [ord(ch) for ch in S]
        self.S = S
        self.a = a + [0]
        self.k = max(self.a) + 1
        self.n = len(self.a)
        self.sa = self.SA_IS(self.a, self.n, self.k)
        # Construct LCP disjoint sparse table
        self.rank = [0] * self.n
        for i, item in enumerate(self.sa):
            self.rank[item] = i
        self.lcp = self.build_LCP(self.a, self.sa, self.rank)
        self.lcp_dst = DisjointSparseTable(self.lcp, op=lambda a, b: min(a, b), e=10 ** 9)

    # Find the start or end of each bucket
    def get_buckets(self, a, k, end=True):
        bucket = [0] * k
        for item in a:
            bucket[item] += 1
        sumation = 0
        for i in range(k):
            sumation += bucket[i]
            if end:
                bucket[i] = sumation
            else:
                bucket[i] = sumation - bucket[i]
        return bucket

    def induce_SAl(self, a, sa, n, k, lstype):
        bucket = self.get_buckets(a, k, end=False)
        for i in range(n):
            j = sa[i] - 1
            if j >= 0 and (not lstype & (1 << j + 1)):
                sa[bucket[a[j]]] = j
                bucket[a[j]] += 1

    def induce_SAs(self, a, sa, n, k, lstype):
        bucket = self.get_buckets(a, k, end=True)
        for i in range(n - 1, -1, -1):
            j = sa[i] - 1
            if j >= 0 and lstype & (1 << j + 1):
                bucket[a[j]] -= 1
                sa[bucket[a[j]]] = j

    def is_LMS(self, index, lstype):
        return lstype >> (index + 1) & 1 and not (lstype >> index & 1)

    def is_stype(self, index, lstype):
        return lstype >> (index + 1) & 1

    def SA_IS(self, a, n, k):
        # L-type or S-type
        # LS-type array in bits, 1-indexed, initialized with S-type first
        lstype = 1
        prev_type = 0
        prev_item = self.k
        for i, item in enumerate(a[::-1]):
            shift = n - i
            if item == prev_item:
                lstype |= prev_type << shift
            elif item < prev_item:
                lstype |= 1 << shift
                prev_type = 1
            else:
                prev_type = 0
            prev_item = item
        # Bucket array
        bucket = self.get_buckets(a, k)
        # Find ends of buckets
        sa = [-1] * n
        for i in range(n - 1, 0, -1):
            if self.is_LMS(i, lstype):
                bucket[a[i]] -= 1
                sa[bucket[a[i]]] = i
        self.induce_SAl(a, sa, n, k, lstype)
        self.induce_SAs(a, sa, n, k, lstype)

        lcm_cnt = 0
        for i in range(n):
            if self.is_LMS(sa[i], lstype):
                sa[lcm_cnt] = sa[i]
                lcm_cnt += 1
        for i in range(lcm_cnt, n):
            sa[i] = -1

        # Rename LCM strings
        name = 1;
        prev = sa[0]
        sa[lcm_cnt + sa[0] // 2] = 0
        for pos in sa[1: lcm_cnt]:
            diff = False
            for d in range(n):
                if a[pos + d] != a[prev + d] or (self.is_stype(pos + d, lstype) != self.is_stype(prev + d, lstype)):
                    diff = True
                    break
                elif d > 0 and (self.is_LMS(pos + d, lstype) or self.is_LMS(prev + d, lstype)):
                    break
            if diff:
                name += 1;
                prev = pos
            pos //= 2
            sa[lcm_cnt + pos] = name - 1
        sub_a = []
        for i in range(lcm_cnt, n):
            if sa[i] >= 0:
                sub_a.append(sa[i])

        # Recursively sort LMS sub strings
        if name < lcm_cnt:
            sub_sa = self.SA_IS(sub_a, len(sub_a), name + 1)
        else:
            sub_sa = sa[:lcm_cnt]
            for i in range(lcm_cnt):
                sub_sa[sub_a[i]] = i
        bucket = self.get_buckets(a, k, end=True)
        j = 0
        for i in range(1, n):
            if self.is_LMS(i, lstype):
                sub_a[j] = i
                j += 1
        # Earn correctly sorted LCMs
        for i in range(lcm_cnt):
            sa[i] = sub_a[sub_sa[i]]
        for i in range(lcm_cnt, n):
            sa[i] = -1
        for i in range(lcm_cnt - 1, -1, -1):
            j = sa[i];
            sa[i] = -1
            bucket[a[j]] -= 1
            sa[bucket[a[j]]] = j

        # Correct induced sorting
        self.induce_SAl(a, sa, n, k, lstype)
        self.induce_SAs(a, sa, n, k, lstype)
        return sa

    def build_LCP(self, a, sa, rank):
        # Add sentinel
        sa.append(-1)
        lcp = [0] * len(a)
        same_cnt = 0
        for index1 in range(len(a)):
            if same_cnt != 0:
                same_cnt -= 1
            index2 = sa[rank[index1] + 1]
            while a[index1 + same_cnt] == a[index2 + same_cnt]:
                same_cnt += 1
            lcp[rank[index1]] = same_cnt
        # Remove sentinel
        sa.pop()
        return lcp

    def get_lcp(self, l, r):
        """ (0-indexed) """
        rank_l = self.rank[l]
        rank_r = self.rank[r]
        if rank_l > rank_r:
            rank_l, rank_r = rank_r, rank_l
        return self.lcp_dst.fold(rank_l, rank_r)

    def contain(self, T):
        """
        文字列 T が S 内に含まれているかどうか
        """
        l = 0
        r = self.n-1
        L = len(T)
        while r-l>1:
            mid = (l+r)//2
            if self.S[self.sa[mid]:self.sa[mid]+L]<T:
                l=mid
            else:
                r=mid
        return T==self.S[self.sa[r]:self.sa[r]+L]

###################################################################
import sys
input = sys.stdin.readline
S = input().rstrip()
SA = SuffixArray(S)
print(len(S)*(len(S)+1)//2-sum(SA.lcp))

Submission status: Time Limit Exceeded

Solution code:
from functools import cmp_to_key


def make_suffix_array(s):
    n = len(s)
    sa = list(range(n))
    rnk = [ord(c) for c in s]
    tmp = [0] * n
    k = 1
    while k < n:
        def cmp(x, y):
            if rnk[x] != rnk[y]:
                return rnk[x] - rnk[y]
            rx, ry = -1, -1
            if x + k < n:
                rx = rnk[x + k]
            if y + k < n:
                ry = rnk[y + k]
            return rx - ry
        sa.sort(key=cmp_to_key(cmp))
        tmp[sa[0]] = 0
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i - 1]]
            if cmp(sa[i - 1], sa[i]):
                tmp[sa[i]] += 1
        tmp, rnk = rnk, tmp
        k *= 2
    return sa


def make_lcp_array(s, sa):
    s = [ord(c) for c in s]
    n = len(s)
    rnk = [None] * 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 = make_suffix_array(S)

result = len(S) * (len(S) + 1) // 2
for x in make_lcp_array(S, sa):
    result -= x
print(result)

Submission status: Time Limit Exceeded

Solution code:
s=input()
c=0
l=[]
for i in range(len(s)):
	for j in range(i+1,len(s)+1):
		if s[i:j] not in l:
			l.append((s[i:j]))
			c+=1
print(c)