結果

問題 No.1018 suffixsuffixsuffix
ユーザー shotoyooshotoyoo
提出日時 2021-05-09 13:12:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 220 ms / 2,000 ms
コード長 5,863 bytes
コンパイル時間 147 ms
コンパイル使用メモリ 81,776 KB
実行使用メモリ 106,136 KB
最終ジャッジ日時 2024-09-18 19:26:31
合計ジャッジ時間 7,169 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
53,732 KB
testcase_01 AC 34 ms
53,760 KB
testcase_02 AC 34 ms
53,632 KB
testcase_03 AC 40 ms
53,504 KB
testcase_04 AC 36 ms
53,120 KB
testcase_05 AC 34 ms
53,760 KB
testcase_06 AC 36 ms
54,144 KB
testcase_07 AC 36 ms
53,120 KB
testcase_08 AC 37 ms
53,632 KB
testcase_09 AC 200 ms
99,456 KB
testcase_10 AC 201 ms
100,096 KB
testcase_11 AC 200 ms
101,656 KB
testcase_12 AC 195 ms
100,224 KB
testcase_13 AC 192 ms
100,608 KB
testcase_14 AC 207 ms
99,968 KB
testcase_15 AC 217 ms
100,608 KB
testcase_16 AC 220 ms
102,268 KB
testcase_17 AC 202 ms
98,432 KB
testcase_18 AC 196 ms
98,304 KB
testcase_19 AC 73 ms
96,384 KB
testcase_20 AC 74 ms
98,048 KB
testcase_21 AC 102 ms
98,440 KB
testcase_22 AC 78 ms
98,092 KB
testcase_23 AC 80 ms
98,688 KB
testcase_24 AC 210 ms
103,904 KB
testcase_25 AC 212 ms
104,592 KB
testcase_26 AC 211 ms
103,552 KB
testcase_27 AC 210 ms
104,828 KB
testcase_28 AC 220 ms
104,192 KB
testcase_29 AC 91 ms
91,904 KB
testcase_30 AC 100 ms
92,288 KB
testcase_31 AC 93 ms
92,160 KB
testcase_32 AC 93 ms
92,160 KB
testcase_33 AC 87 ms
91,776 KB
testcase_34 AC 36 ms
53,632 KB
testcase_35 AC 78 ms
98,280 KB
testcase_36 AC 84 ms
92,416 KB
testcase_37 AC 215 ms
106,136 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda : sys.stdin.readline().rstrip()

sys.setrecursionlimit(2*10**5+10)
write = lambda x: sys.stdout.write(x+"\n")
debug = lambda x: sys.stderr.write(x+"\n")
writef = lambda x: print("{:.12f}".format(x))


def sa_naive(s):
    n = len(s)
    sa = list(range(n))
    sa.sort(key=lambda x: s[x:])
    return sa

def sa_doubling(s):
    n = len(s)
    sa = list(range(n))
    rnk = s
    tmp = [0] * n
    k = 1
    while k < n:
        sa.sort(key=lambda x: (rnk[x], rnk[x + k])
                if x + k < n else (rnk[x], -1))
        tmp[sa[0]] = 0
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i - 1]]
            if sa[i - 1] + k < n:
                x = (rnk[sa[i - 1]], rnk[sa[i - 1] + k])
            else:
                x = (rnk[sa[i - 1]], -1)
            if sa[i] + k < n:
                y = (rnk[sa[i]], rnk[sa[i] + k])
            else:
                y = (rnk[sa[i]], -1)
            if x < y:
                tmp[sa[i]] += 1
        k *= 2
        tmp, rnk = rnk, tmp
    return sa

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 < 10:
        return sa_naive(s)
    if n < 50:
        return sa_doubling(s)
    ls = [0] * 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 ls[i]:
            sum_l[s[i] + 1] += 1
        else:
            sum_s[s[i]] += 1
    for i in range(upper):
        sum_s[i] += sum_l[i]
        if i < upper:
            sum_l[i + 1] += sum_s[i]
    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)
    sa = [-1] * n
    buf = sum_s.copy()
    for d in lms:
        if d == n:
            continue
        sa[buf[s[d]]] = d
        buf[s[d]] += 1
    buf = sum_l.copy()
    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
    buf = sum_l.copy()
    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
    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 < 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]]
        sa = [-1] * n
        buf = sum_s.copy()
        for d in sorted_lms:
            if d == n:
                continue
            sa[buf[s[d]]] = d
            buf[s[d]] += 1
        buf = sum_l.copy()
        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
        buf = sum_l.copy()
        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
    return sa

def suffix_array(s, upper=255):
    if type(s) is str:
        s = [ord(c) for c in s]
    return sa_is(s, upper)

def lcp_array(s, sa):
    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
def z_algorithm(s):
    """
    各iについてs[0..n)とs[i..n)のLCP(Longest Common Prefix)の長さを求める
    s: str or (list of int )
    """
    n = len(s)
    if n==0:
        return []
    z = [None]*n
    z[0] = 0
    j = 0
    for i in range(1,n):
        k = 0 if j + z[j] <= i else min(j+z[j]-i, z[i-j])
        z[i] = k
        while i+k<n and s[k]==s[i+k]:
            k += 1
        z[i] = k
        if j+z[j] < i+z[i]:
            j = i
    z[0] = n
    return z

n,m,q = list(map(int, input().split()))
s = input()
ks = list(map(int, input().split()))
z = z_algorithm(s)
for i in range(1,n):
    if z[i]==n-i:
        o = i
        break
else:
    o = 0
if o>0 and n%o==0:
    s = s[:o]
    m = m * (n//o)
    n = o
sa = suffix_array(s+s)
ans = []
c = 0
j = 0
for v in sa:
    if v<n:
        while j<q and ks[j]<=c+(m-1):
            vv = v + n * (m-2-(ks[j]-c-1))
            ans.append(vv)
            j += 1
        c += m-1
    else:
        if j<q and ks[j]==c+1:
            ans.append(v-n + n * (m-1))
            j += 1
        c += 1
write(" ".join(map(str, [v+1 for v in ans])))
0