結果
問題 | No.1018 suffixsuffixsuffix |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
from bisect import bisect_left as blfrom bisect import bisect_right as brdef SA_IS(a):a += [0]k = max(a) + 1n = len(a)def induce_l(sa, a, n, k, stype):bucket = get_buckets(a, k, 1)for i in range(n):j = sa[i] - 1if j >= 0 and (not stype[j]):sa[bucket[a[j]]] = jbucket[a[j]] += 1def induce_s(sa, a, n, k, stype):bucket = get_buckets(a, k, 0)for i in range(n)[::-1]:j = sa[i] - 1if j >= 0 and stype[j]:bucket[a[j]] -= 1sa[bucket[a[j]]] = jdef get_buckets(a, k, start = 0):bucket = [0] * kfor item in a:bucket[item] += 1s = 0for i in range(k):s += bucket[i]bucket[i] = s - (bucket[i] if start else 0)return bucketdef set_lms(a, n, k, default_order):bucket = get_buckets(a, k)sa = [-1] * nfor i in default_order[::-1]:bucket[a[i]] -= 1sa[bucket[a[i]]] = ireturn sadef 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 sadef rename_LMS_substring(sa, a, n, stype, LMS, l):sa = [_s for _s in sa if LMS[_s]]tmp = [-1] * (n//2) + [0]dupl = 0for _ 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]:breakif ii and (LMS[i+ii] or LMS[j+ii]):dupl += 1breaktmp[j//2] = _ - dupltmp = [t for t in tmp if t >= 0]return tmp, dupldef calc(a, n, k):stype = [1] * nfor 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] = 0LMS = [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] * lfor i in range(l):sub_sa[renamed_LMS[i]] = ilms = [lms[sub_sa[i]] for i in range(l)]sa = induce(a, n, k, stype, lms)return sasa = calc(a, n, k)return saN, 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 *= MSA = 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 // iN = ibreakS *= 2SA = SA_IS(S)[1:]X = []i = 0for 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 += 1else:# X.append((i, s))X.append((i << 47) + (M-2) * N + s + 1)i += M-1def 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) - 1a, b = chk(X[t])return b - (k - a) * N + 1print(*[calc(k) for k in K])