string

詰め合わせです。

suffix_array_upper

listに対してsuffix-arrayを求めます

suffix_array

stringに対してsuffix-arrayを求めます

lcp_array

lcp-array(Longest Common Prefix)を求めます。 呼び出す際には事前にsuffix_arrayのリストを持つことが要求されます。

z_algorithm

z配列を求めます。

使用例

(https://atcoder.jp/contests/practice2/tasks/practice2_i)

class string:
    # (中略)

S=input()
sa=string.suffix_array(S)
answer=(len(S)*(len(S)+1))//2
for x in string.lcp_array(S,sa):
    answer-=x
print(answer)