結果

問題 No.1018 suffixsuffixsuffix
ユーザー Kiri8128
提出日時 2020-04-04 01:49:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 392 ms / 2,000 ms
コード長 3,802 bytes
コンパイル時間 264 ms
コンパイル使用メモリ 82,296 KB
実行使用メモリ 124,160 KB
最終ジャッジ日時 2024-07-03 06:42:54
合計ジャッジ時間 9,438 ms
ジャッジサーバーID
(参考情報)
judge1 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

from bisect import bisect_left as bl
from bisect import bisect_right as br
def SA_IS(a):
a += [0]
k = max(a) + 1
n = len(a)
def induce_l(sa, a, n, k, stype):
bucket = get_buckets(a, k, 1)
for i in range(n):
j = sa[i] - 1
if j >= 0 and (not stype[j]):
sa[bucket[a[j]]] = j
bucket[a[j]] += 1
def induce_s(sa, a, n, k, stype):
bucket = get_buckets(a, k, 0)
for i in range(n)[::-1]:
j = sa[i] - 1
if j >= 0 and stype[j]:
bucket[a[j]] -= 1
sa[bucket[a[j]]] = j
def get_buckets(a, k, start = 0):
bucket = [0] * k
for item in a:
bucket[item] += 1
s = 0
for i in range(k):
s += bucket[i]
bucket[i] = s - (bucket[i] if start else 0)
return bucket
def set_lms(a, n, k, default_order):
bucket = get_buckets(a, k)
sa = [-1] * n
for i in default_order[::-1]:
bucket[a[i]] -= 1
sa[bucket[a[i]]] = i
return sa
def induce(a, n, k, stype, default_order):
sa = set_lms(a, n, k, default_order)
induce_l(sa, a, n, k, stype)
induce_s(sa, a, n, k, stype)
return sa
def rename_LMS_substring(sa, a, n, stype, LMS, l):
sa = [_s for _s in sa if LMS[_s]]
tmp = [-1] * (n//2) + [0]
dupl = 0
for _ in range(1, l):
i, j = sa[_-1], sa[_]
for ii in range(n):
if a[i+ii] != a[j+ii] or stype[i+ii] != stype[j+ii]:
break
if ii and (LMS[i+ii] or LMS[j+ii]):
dupl += 1
break
tmp[j//2] = _ - dupl
tmp = [t for t in tmp if t >= 0]
return tmp, dupl
def calc(a, n, k):
stype = [1] * n
for i in range(n-1)[::-1]:
if a[i] > a[i+1] or (a[i] == a[i+1] and stype[i+1] == 0):
stype[i] = 0
LMS = [1 if stype[i] and not stype[i-1] else 0 for i in range(n-1)] + [1]
l = sum(LMS)
lms = [i for i in range(n) if LMS[i]]
sa = induce(a, n, k, stype, lms)
renamed_LMS, dupl = rename_LMS_substring(sa, a, n, stype, LMS, l)
if dupl:
sub_sa = calc(renamed_LMS, l, l - dupl)
else:
sub_sa = [0] * l
for i in range(l):
sub_sa[renamed_LMS[i]] = i
lms = [lms[sub_sa[i]] for i in range(l)]
sa = induce(a, n, k, stype, lms)
return sa
sa = calc(a, n, k)
return sa
N, M, Q = map(int, input().split())
S = [ord(a)-96 for a in input()]
K = [int(a)-1 for a in input().split()]
if S.count(S[0]) == N:
print(*[N * M - k for k in K])
elif M <= 2:
S *= M
SA = SA_IS(S)[1:]
print(*[SA[k] + 1 for k in K])
else:
for i in range(1, int(N**0.5)+2):
if N % i == 0 and S[i:] == S[:-i]:
S = S[:i]
M *= N // i
N = i
break
S *= 2
SA = SA_IS(S)[1:]
X = []
i = 0
for s in SA:
if s >= N:
# X.append((i, (M-1) * N + (s - N)))
X.append((i << 47) + (M-1) * N + (s - N) + 1)
i += 1
else:
# X.append((i, s))
X.append((i << 47) + (M-2) * N + s + 1)
i += M-1
def chk(a):
return (a >> 47, a - (a >> 47 << 47) - 1)
# print("X =", [chk(x) for x in X])
X = sorted(X)
# print("SA =", SA)
# print("X =", X)
# print("X =", [chk(x) for x in X])
def calc(k):
t = bl(X, k + 1 << 47) - 1
a, b = chk(X[t])
return b - (k - a) * N + 1
print(*[calc(k) for k in K])
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0