class string: def sa_is(s,upper): n=len(s) if n==0: return [] if n==1: return [0] if n==2: if (s[0]=1 and 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 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=sorted_lms[i-1] r=sorted_lms[i] end_l=lms[lms_map[l]+1] if (lms_map[l]+1=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 1: m = (l + r) // 2 k = SA[m] R = [] for j in range(n): R.append(S[j+k]) R = ''.join(R) if R < T: l = m else: r = m t = r # [0,s) l = -1 r = N while r - l > 1: m = (l + r) // 2 k = SA[m] R = [] for j in range(n): R.append(S[j+k]) R = ''.join(R) if R > T: r = m else: l = m s = r # SAの[t,s)間の個数 ans += s - t print(ans)